[BOJ_15650] N과 M (2)

설명

---

문제 설명을 보면 알겠지만 조합을 이용한다.

 

즉, 순서가 상관이 없는 경우다 1 2 3 4 = 4 3 2 1 이기 때문에 모두 순서가 같은 경우의 수는 배제한다. 이때 조합을 사용하면 되는데 아래 코드로 설명하면 start가 시작 지점이고 이 때 부터 N 까지 오름차순으로 증가하며 필요한 값을 집어 넣게 된다.

 

처음 보면 재귀의 형태가 잘 그려지지 않아서 햇갈릴 수 있지만 아래 코드를 먼저 보고 나서 그림으로 보면 조금 더 쉬울 수도 있을 것 같다.

 

반복문 내부에서 나아가는 것을 생각하면 이해하기 쉽다.

출력 부가 선 마지막에서 실행이 되는데 이때까지 들어온 arr 값을 출력하게 된다. 밑에서 부터 1,2 / 1,3 / 1,4 / 인데 나아가는 선이 각각 다음 수를 선택하는 선으로 봐주면 될 것 같다. start는 2이지만 2,3,4로 시작하니 1 이후로는 2,3,4가 선택이 된 것이고 두번째 선으로 부터 시작하는 것은 2로 시작하여 2,3 / 2,4 이렇게 선택이 된다. 3으로 선택된 선도 마찬가지로 3,4로 선택이 되고 종료되는 것을 확인 할 수 있다.

 

코드

---

package backtracking;

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

public class BOJ_15650 {
    static int arr[];
    static int N,M;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());

        arr = new int[M];

        dfs(0,1);
    }
    private static void dfs(int idx,int start) {
        if(idx == M){
            for(int i = 0; i < arr.length; i++)
            {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for(int i = start; i <= N; i++){
            arr[idx] = i;
            dfs(idx+1,i+1);
        }
    }
}

15650번: N과 M (2)