[백트래킹] N과 M(4)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
• 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

비 내림차순.

배열을 출력할 때, 

11, 12 이런 건 가능, 근데 21 32 이런건 안된다는 것

 

어떻게 해결해야할까?

1. if문으로 arr[i-1] 이 arr[i] 보다 큰 경우는 그냥 return 하게 만들면 되지 않을까?

 

import java.util.*;
import java.io.*;

public class Main{
    public static int[] arr;
    public static int N,M;
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String args[])throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        dfs(0);
        System.out.println(sb);
        
    }
    
    public static void dfs(int depth){
        if(depth == M){
            for(int i=0;i<N;i++){
                if(i>0 && arr[i-1] > arr[i]){
                    return;
                }
                sb.append(arr[i]).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i=1;i<=N;i++){
            arr[depth]=i;
            dfs(depth+1);
        }
    }
}

런타임 에러 발생,,

 

https://st-lab.tistory.com/117

[백준] 15652번 : N과 M (4) - JAVA [자바]

import java.util.*;
import java.io.*;

public class Main{
    public static int[] arr;
    public static int N,M;
    public static StringBuilder sb = new StringBuilder();
    
    public static void main(String args[])throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr=new int[M];
        dfs(1,0); //1과 0을 매개변수로 넘겨준다.
        System.out.println(sb);
        
    }
    
    public static void dfs(int at,int depth){
        if(depth == M){
            for(int val:arr){
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i=at;i<=N;i++){
            arr[depth]=i;
            dfs(i,depth+1);
        }
    }
}

at을 사용하여 at이후의 숫자부터 시작하도록 사용했다. 

아하!

at을 이용하면 되는 구나