백준-15649번/N과 M(2) (java)

 

 

문제 접근

 

이 문제는 N과M(1)와는 다르게 오름차순으로 정렬된 상태로 출력을 해야한다.

처음에는 어렵게 느껴질 수 있지만 N과M(1)보다 간단한 문제이다.

 

문제 해결

 

N과M(1)과 마찬가지로 DFS를 이용한다.

private 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+1,depth+1);
    }

}

 

at은 1부터 depth는 0부터 시작하여 dfs함수내부의 for문에서 arr배열에 출력할 숫자를 추가한다.

** N과M(1)과는 다르게 중복 방문을 검사하는 visit배열(boolean)이 없는 이유 ==> 오름차순으로 출력하기 때문에 중복 될 일이 없다.

 

 

<전체코드>

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

public class Problem15650 {
    static StringBuilder sb = new StringBuilder();
    static int n, m;
    static int[] arr;

    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);
        System.out.println(sb);
    }

    private 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+1,depth+1);
        }

    }
}