[백준] 15650번 : N과 M (2) – JAVA [자바]

https://www.acmicpc.net/problem/15650

 

 

---

문제

 

 

---

해결 방법

이 문제는 백트래킹(Backtracking)을 활용하여 중복 없이 M개의 숫자를 선택하는 순열(Permutation) 문제이다. 다음과 같은 방식으로 해결할 수 있다.

1. 조합(Combination) 개념 활용

• 1부터 N까지의 숫자 중에서 M개를 고른다.
• 선택한 숫자는 오름차순이어야 한다.
• 사전 순으로 출력해야 하므로, 작은 숫자부터 선택한다.

 

2. 백트래킹을 이용한 조합 생성

• start 변수를 활용하여 중복을 방지하고 오름차순을 유지한다.
• for 문을 이용해 start 값부터 N까지 반복하며 숫자를 선택한다.
• 선택한 숫자를 result 배열에 저장하고, 길이가 M이 되면 출력한다.
• 재귀 호출을 통해 다음 숫자를 선택하고, 선택이 끝나면 원상 복구(백트래킹)한다.

 

---

코드 

 

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] result;
    static StringBuilder sb;

    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());
        sb = new StringBuilder();

        result = new int[m];
        backtrack(1, 0);
        System.out.print(sb);
    }

    static void backtrack(int start, int depth) {
        if (depth == m) { // M개를 선택했다면 출력
            for (int num : result) {
                sb.append(num).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i <= n; i++) {
            result[depth] = i; // 선택한 숫자 저장
            backtrack(i + 1, depth + 1); // 다음 숫자 선택 (i+1로 중복 방지)
        }
    }
}

 

 

---

코드 설명

1. backtrack(int start, int depth)

• depth == m이면 출력 (M개 선택 완료)
• for문을 start부터 N까지 돌며 숫자를 선택
• i + 1을 다음 호출의 start로 전달하여 중복 방지

 

2. 오름차순 보장

• start를 이용하여 숫자를 순서대로 선택하므로 자동으로 오름차순이 유지됨

 

3. visited 배열 없이 해결

• visited[] 대신 start 값을 활용하여 중복 없이 선택 가능
• 메모리 사용량이 줄어들고, 코드가 더 간결해짐

 

백트래킹 흐름 예시

예제 입력: N = 4, M = 2

단계	result [] 상태	start 값	재귀 호출
1	[1, _]	1 → 2	backtrack(2, 1) 호출
2	[1, 2]	2 → 3	backtrack(3, 2) 호출 → 출력: 1 2
3	[1, 3]	3 → 4	backtrack(4, 2) 호출 → 출력: 1 3
4	[1, 4]	4 → 5	backtrack(5, 2) 호출 → 출력: 1 4
5	[2, _]	2 → 3	backtrack(3, 1) 호출
6	[2, 3]	3 → 4	backtrack(4, 2) 호출 → 출력: 2 3
7	[2, 4]	4 → 5	backtrack(5, 2) 호출 → 출력: 2 4
8	[3, _]	3 → 4	backtrack(4, 1) 호출
9	[3, 4]	4 → 5	backtrack(5, 2) 호출 → 출력: 3 4

 

 

최종 출력

1 2
1 3
1 4
2 3
2 4
3 4

 

---

시간 복잡도 분석

1. 조합의 경우의 수

• N개의 숫자에서 M개를 선택하는 조합의 개수는 C(N, M) = N! / (M! * (N-M)!)이다.
• 최댓값인 N = 8, M = 8일 때 P(8,8) = 8! = 40,320이므로 충분히 해결 가능하다.

 

2. 최악의 경우 시간 복잡도

• 최악의 경우에도 O(2^N) 이하로 수행되며, N ≤ 8이므로 충분히 빠름.

 

 

---

결론

• 백트래킹을 사용하여 조합(Combination) 문제를 해결할 수 있다.
• visited 배열 없이 start를 활용하면 코드가 간결해지고 메모리 사용량이 줄어든다.
• 사전 순 정렬이 자동 보장되므로 추가적인 정렬 과정이 필요 없다.