알고리즘 :: 백준 :: DFS :: 6603 :: 로또

문제

로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

문제접근

1. 요소의 개수 K와 집합 S가 주어질 때 만들 수 있는 로또번호 조합을 알아야 한다.
2. 가장 쉽게 떠올리고 접근할 수 있는 방법은 'bruteforce'방법이다.
3. K가 최대 12이므로 가능한 모든 경우의 수는 $12\times 11\times 10\times 9\times 8\times 7 = 665,280$ 이므로 bruteforce도 충분히 유효한 전략이다.
4. 출력하는 모든 조합은 오름차순으로 출력해야하므로 낮은 수부터 선정하는 규칙을 DFS와 함께 사용하는 것이 bruteforce보다 유효한 전략이다.

코드

#include <iostream>
#include <vector>
using namespace std;

static int k;
static vector<int> lotto(13, 0);	// 사용자로부터 입력받는 수열
static vector<int> comb(6, 0);		// 만들어지는 로또번호 조합

void solve(int startIdx, int depth) {
    if (depth == 6) {	// [기저] - 6개의 조합이 만들어졌다면 출력 후 return.
        for (int i = 0; i < 6; ++i) cout << comb[i] << " ";
        cout << '\n';
        return;
    } // 0~k-1 / 1~k-1 / ... / k-1 모든 경우의 수를 따져본다. 
    for (int i = startIdx; i < k; ++i) {
        comb[depth] = lotto[i];		// 숫자 하나 할당하고
        solve(i + 1, depth + 1);	// 다음 깊이(depth)로 이동
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    while (true) {
        cin >> k;   if (k == 0) break;
        for (int i = 0; i < k; ++i) cin >> lotto[i];
        solve(0, 0);
        cout << '\n';
    }
}

• 숫자 하나를 고정해두고 나머지 6-i개의 숫자에 대해 다시 재귀를 돌리면서 숫자 하나씩 고정시키는 전략을 사용한다.

결과