[BOJ15650] N과 M (2)

백준 15650 N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

N과 M 두번째 문제이다. 첫번째 문제는 여기를 참고하자.

 

이전 문제와 다른 점은 '오름차순'이라는 것이다.

오름차순이라고 해서 수열을 배열에 담아 sort하거나, 내가 자체적으로 정렬해줄 필요가 없다는 것은 당연하다.

그렇다면 지난번 문제와 달리 어떻게 작성해야할까?

 

입력이 4 2 라고 가정한다면 N은 4, M은 2로 4개 중 2개만 뽑으면 된다.

N과 M (1) : 1 2, 1 3, 1 4, 2 1, 2 3, 2 4, 3 1, ...

N과 M (2) : 1 2, 1 3, 1 4, 2 3, 2 4, 3, 4

 

둘 다 중복허용이 안되는 것은 동일하나 이번 문제에서는 1 2와 2 1은 동일시 한다.

 

처음엔 당연히 visited 배열로 방문했던 곳을 체크해주며 풀었는데, 아무리 해도 자꾸 N과 M (1)의 답이 나왔다.😭

하지만 오름차순이라는 것에 집중해서 생각해보면 방문했던 곳을 체크해줄 필요가 없다. 다시 돌아올 일이 없기 때문!

함수를 재귀호출 할 때 인자 값만 잘 더해서 호출하면 된다.

 

일단 그래프 깊이를 체크해줄 num과 수열을 채울 start값을 인자로 사용했다.

private static void func(int start, int num) {
        ...
	}

그리고 이제 하나씩 방문해서 배열에 저장 후, 깊이(num)가 2개(M개)가 되면 배열에 든 것을 출력해주고 다시 뒤로 돌아가면 된다.

가장 중요한 것은 재귀호출 할 때 인자 값에 start값을 어떻게 넣어주느냐이다.

 

나는 start값 때문에 거의 다 와서 아주 오래 헤맸다.

start에 +1을 해서 보내면 될 것이라 생각했는데, 그건 1 4 까지만 허용(?)되는 것이고 2 3으로 넘어가지 않고 2 2부터 계속 시작되는 것😭

 

디버깅을 여러번 한 끝에 인자값에 i + 1을 담아줬고, 바로 성공✨

private static void func(int start, int num) {
        ...

        for(int i = start; i <= N; i++){
            res[num] = i;
            func(i + 1, num + 1);
        }
    }

백트래킹이든 DFS, BFS 모두 간단한 예제를 종이에 그려보면서 필요한 인자값도 찾고, 어떻게 로직이 진행되는지도 살펴보는걸 습관들여야겠다는 생각이 매번 든다...

 

제출 코드는 아래와 같다.

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

public class BOJ15650 {
    static int N, M;
    static int[] res;
    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());
        res = new int[M + 1];

        func(1, 0);

        System.out.println(sb);
    }

    private static void func(int start, int num) {
        if(num == M){
            for(int i = 0; i < M; i++){
                sb.append(res[i] + " ");
            }
            sb.append("\n");
            return;
        }

        for(int i = start; i <= N; i++){
            res[num] = i;
            func(i + 1, num + 1);
        }
    }
}