프로그래밍/알고리즘

BOJ 6603 · 로또

반응형


알고리즘 분류 : 브루트 포스  


K개의 숫자 중에서 6개를 뽑아서 나열하는 문제다. 재귀 함수를 이용하여 간단히 구현할 수 있지만, 조합(Combination)을 이용한 방법으로도 구현할 수 있다.

C++의 STL에 조합(combination)이 없으므로, 순열(permutation)을 이용해야 한다. 

Python은 itertools에 있는 combinations를 이용하면 간단하다.


  • 순열을 응용하여 조합을 만들 수 있다.
  • N 개의 숫자가 있는 리스트 A에서 K 개의 숫자를 뽑는다면, nCk 라고 표기한다.
  • 1이 K 개, 0이 N-K 개로 구성된 N 사이즈의 리스트 B를 생성한다. 예를 들어 8C6이라고 했을 때, 11111100 처럼 만든다.
  • 리스트 B를 prev_permutation을 통해 순열로 돌리면서 루프를 돈다.
  • 그리고 N 번 반복하는 for 문을 루프 내에 구성하여 B 리스트 원소의 값이 1일 경우, 같은 인덱스의 A 리스트의 값을 출력한다.
  • 내림차 순으로 출력해야 한다면, 리스트 B의 순서를 반대로 뒤집고 next_permutation를 이용하면 된다.




C++ 소스코드


#include <cstdio>
#include <algorithm>
using namespace std;

void solve(int n) {
    int c[n] = {0, };
    for (int i=0; i<6; i++) c[i] = 1;
    int a[n];
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    do {
        for (int i=0; i<n; i++) {
            if (c[i]) printf("%d ", a[i]);
        }
        printf("\n");
    } while (prev_permutation(c, c+n));
    printf("\n");
}

int main() {
    int n;
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        solve(n);
    }
    return 0;
}


✓ 재귀 함수를 이용하여 구현할 수 있다. solve() 함수 수정.


void solve(int cnt, int index, vector<int> &lotto) {
    if (cnt == 6) {
        for (auto i : lotto) printf("%d ", i);
        printf("\n");
        return;
    }
    if (index >= n) return;
    lotto.push_back(a[index]);
    solve(cnt+1, index+1, lotto);
    lotto.pop_back();
    solve(cnt, index+1, lotto);
}




Python 3 소스코드


from itertools import combinations
while True:
    a = input().split()
    if a.pop(0) == '0': break
    for a in combinations(a, 6):
        print(" ".join(a))
    print()




참고



반응형