[백준 15652] N과 M (4) [java]

---

이 문제의 핵심은 비내림차순으로 출력해야 한다는 점이다.

 

즉, 처음 나온 숫자보다 큰거나 같은 수가 옆에 나와야 한다는 것이다.

 

dfs방법으로 문제를 풀건데

 

원리는 간단하다.

 

만약 4 4를 입력받은 경우,

우선 가장 처음 나올 수 있는 수는 

1 1 1 1 

 

그다음에 나오는 수는

1 1 1 2

 

그다음은

1 1 1 3 이렇게 만들 수 있다.

 

쉽게 풀어보자면 배열의 길이를 depth로 보는 것이다.

즉 배열을 끝까지 다 채우면 depth를 만족시키고 return시키는 것이다.

 

return된 다음에는 마지막 1이 들어간 부분만 2로 바꿔주면 된다.

 

지금까지 설명한 방법은 N과 M(3)을 푸는 방법이다.

N과 M(4)에는 비내림차순이라는 조건이 추가됐는데 이것은 dfs를 호출할 때 현재 내 앞에 숫자를 알고 그 숫자보다 크거나 같은 수들만 추가해주는 것이다.

 

코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N_M_4 {
    static int N;
    static int M;
    static int[] arr;
    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[N];

        dfs(1,0);
        System.out.println(sb);
    }

    public static void dfs(int cur,int depth){
        if(depth == M){
            for(int i = 0; i<M;i++){
                sb.append(arr[i]).append(' ');
            }
            sb.append("\n");
            return;
        }
        for(int i = cur;i<=N;i++){

            arr[depth] = i;
            dfs(i,depth+1);
        }
    }
}