[백준] 15651번: N과 M (3)

💡문제 분석 요약

“1부터 N까지 자연수 중에서 M개를 고른 수열” 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다. 같은 수를 여러 번 골라도 된다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

💡알고리즘 설계

• N, M을 입력받는다.
• 수열을 저장할 `sequence` 배열을 생성한다.
• 백트래킹을 사용해 길이가 M인 모든 가능한 수열을 생성한다.
  • 현재 깊이(`depth`)가 M과 같아지면 수열을 출력한다.
  • 1부터 N까지의 수에 대해:
    • 현재 수를 수열에 추가한다.
    • `depth + 1` 깊이로 재귀 호출한다.

 

💡코드

import java.io.*;

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

    static void backtracking(int depth) {
        if(depth == m) {
            for(int num : sequence) {
                sb.append(num + " ");
            }
            sb.append("\\n");
            return;
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        sequence = new int[m];

        int depth = 0;
        backtracking(depth);

        System.out.println(sb);
    }
}

 

💡시간복잡도

N개를 M번 반복하기 때문에 시간복잡도는 $O(N^M)$ 이다.

 

💡 느낀점 or 기억할정보

15663번 “N과 M (9)” 문제보다는 쉬웠던 것 같다. 15663번 문제는 중복을 허용하지 않고, 오름차순 정렬이 필요해서 좀 더 복잡했는데, 이 문제는 중복도 허용하고 정렬도 불필요했다.

이 문제는 단순한 형태의 백트래킹으로 구현했지만, 좀 더 복잡한 문제가 나오면 어려워질 것 같다.