(15651) N과 M(3)

문제

문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.

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

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

---

문제 풀이

해당 문제는 백트래킹이라기 보다는 재귀함수를 이해를 얼마나 하였냐에 따라 문제 난이도가 나뉘는 문제이다. 현재 출력되는 값을 보면 같은 값이 출력이 되고 있는데, 해당 방식으로 출력 된다는 것은 순서나 반복여부를 따지지 않고 길이에 따른 출력만 잘해주면 된다는 뜻이다. 

 

그러므로 출력 조건은 depth가 m 과 같아지면 출력을 진행하게 하면된다. 

 

여기서 출력을 배열값을 System.out.print를 수행하게 되면 시간초과가 된다. 그러므로 StringBuilder를 사용을 하여 처리 하는 방향으로 해야 문제가 없다. <-- 일부러 문제를 꼬아서 낸 듯 하다...

---

나의 답안

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        arr = new int[m];

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

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

        for (int i = 1; i <= n; i++) {
            arr[depth] = i;
            dfs(depth + 1);
        }
    }
}