[C++] 백준 BOJ 6603 로또

문제링크 : https://noj.am/6603

N개의 원소를 가지는 집합에서 K개를 고르는 조합(Combination) 문제로 STL의 permutation을 사용하면 쉽게 풀 수 있다.

algorithm 헤더에 있는 next_permutation()과 prev_permutation()으로 순열을 구할 수 있다.

[1, 2, 3, 4]를 next_permutation()을 사용하면

[1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 2, 3] ..... 이런 식으로 사전 순서대로 순열이 적용된다.

prev_permutation()은 그 반대라고 볼 수 있다.

그렇다면 조합을 사용하려면 어떻게 해야할까?

[1, 1, 0, 0]을 prev_permutation()으로 돌려보면 아래와 같은 값을 얻을 수 있다.

[1, 0, 1, 0] [1, 0, 0, 1] [0, 1, 1, 0] [0, 1, 0, 1] [0, 0, 1, 1]

중복된 원소들은 제외하고 순열을 만들어 주는 것을 확인할 수 이다.

위의 순서를 잘 살펴보면 N개의 집합에서 K개를 고르는 조합의 순서와 동일하다는 사실을 알 수 있다!

따라서, 4개의 원소를 가지는 집합에서 2개를 고르는 방법은 아래와 같이 표현 가능하다.

[1, 1, 0, 0] [1, 0, 1, 0] [1, 0, 0, 1] [0, 1, 1, 0] [0, 1, 0, 1] [0, 0, 1, 1] - A

[1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4] - B

A 배열에서 1의 값을 가지는 인덱스를 B에서 출력해주면 된다.

이를 표현하면 if( A[idx] == 1 ) cout << B[idx]; 가 되겠다.

자료형을 bool 타입으로 사용한다면 조금이나마 메모리 공간을 줄일 수 있다.

// BOJ 6603 로또
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int n = 1234;
    while (cin >> n && n != 0) {
        vector<int> num(n);
        for (int i = 0; i < n; i++)
            cin >> num[i];
        // nCr을 위한 배열
        vector<bool> comb(n, false);
        for (int i = 0; i < 6; i++)
            comb[i] = true;
        do {
            for (int i = 0; i < n; i++)
                if (comb[i])
                    cout << num[i] << ' ';
            cout << '\n';
        } while (prev_permutation(comb.begin(), comb.end()));
        cout << '\n';
    }
    return 0;
}
 

다른 풀이법으로는 DFS를 이용한 백트래킹 방법이 있다.

DFS처럼 탐색하되 사이즈가 '6'이 되면 탐색을 중단하고 스택에 쌓여있는 다음 dfs로 넘어가는 방법이다.

이 방법으로 완전탐색을 시행하면 된다. 그리고, 남은 노드의 갯수가 6 이하면 탐색을 할 필요가 전혀 없으므로 해당 조건을 추가해주었다.

// BOJ 6603 로또
#include <iostream>
#include <vector>
 
using namespace std;
 
int n = 1234;
vector<int> num;
vector<int> result;
 
void dfs(int idx) {
    // 6개를 채우면 출력하고 dfs 탐색 중단
    if (result.size() == 6) {
        for (int r : result)
            cout << r << ' ';
        cout << '\n';
        return;
    }
    for (int i = idx; i < n; i++) {
        // 남은 노드 수가 6 이하면 탐색할 필요 없음
        if(n - i + result.size() < 6) return;
        result.push_back(num[i]);
        dfs(i + 1);
        result.pop_back();
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    while (cin >> n && n != 0) {
        num = vector<int>(n);
        for (int i = 0; i < n; i++)
            cin >> num[i];
 
        dfs(0);
 
        cout << '\n';
    }
    return 0;
}