15650번: N과 M(2)

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

 

문제

 

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

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

입력

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

출력

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

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

 

풀이

---

 해당 문제에서 경우의 수는 1<=M<=N<=8로 꽤나 범위가 작은 편이다. 따라서 조합의 개수는 70개밖에 되지 않는다. 따라서 백트래킹으로 해결할 수 있다.

 

처음에는 queue를 이용해서 중복없이 M을 구하려고 했는데, 문제에서 요구하는 것은 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열이라는 점, 고른 수열은 항상 오름차순이어야 하는 점을 지키지 못했다.

 

그리고 애초에 queue는 FIFO로 앞을 꺼내고 뒤를 추가하는 방식인데 조합에서는 각 수를 선택한 상태에서 다음 수를 선택하는 재귀적 탐색이 필요하다. 내가 시도한 등차 수열 접근법은 논리적으로 잘못되었다. d라는 변수를 늘려가며 수열을 생성하려고 했는데, 단순히 중복없이 M개의 숫자를 고르고, 그 수열이 오름차순이어야 하는지 확인해야하지, 등차수열을 만드는 문제는 아니었다.

 

 

왜 백트래킹이 적합한가?

---

 나의 첫번째 접근이 잘못되었고 백트래킹이 방식이 맞음을 확인했다. 그런데 왜 조합 문제에서 백트래킹을 활용하는지 궁금했다. 백트래킹은 모든 가능한 조합을 탐색하는 대신, 불필요한 경우는 일찍 포기한다. 다음으로 시작 숫자를 제한하며 재귀적으로 탐색하면 자연스럽게 오름차순을 유지할 수 있다.

 

해당 문제는 모든 가능한 조합을 탐색하는 문제다.

 

따라서 접근방식은 아래가 옳다.

1. 재귀 호출로 현재 위치에서 가능한 모든 수를 선택한다.
2. 오름차순 유지를 위해, 선택한 숫자보다 큰 다음 숫자만 다음에 선택한다.
3. 선택한 숫자가 M개면 출력한다.

 

따라서 최종 코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> combination;

void dfs(int start) {
    if (combination.size() == M) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= N; i++) {
        combination.push_back(i);
        dfs(i + 1); // 다음 숫자 선택
        combination.pop_back(); // 백트래킹
    }
}

int main() {
    cin >> N >> M;
    dfs(1); // 1부터 시작
    return 0;
}

 

느낀점

---

 최근 종강하고 자격증 준비와 계절학기를 병행하다 정말 오랜만에 알고리즘 문제를 접했는데, 이전까지 내가 부족하다고 생각했던 백트래킹이 여전히(당연히) 아직 백트래킹 문제인지 인지하는 것도 어려웠다. 이와 관련된 문제를 더 풀어봐야겠다는 생각을 했다.

 

파이팅!!