[BOJ 6603 // C++] 로또

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15610번 문제인 Abbey Courtyard이다.
문제는 아래 링크를 확인하자.

 

www.acmicpc.net/problem/6603

6603번: 로또

이 문제는 오름차순으로 주어진 숫자들 가운데 6개의 수를 고르는 경우의 수를 빠짐없이 나열하는 문제이다.

모든 경우를 나열해야하므로 가능한 모든 경우를 일일이 탐색하자.

recursion을 이용하면 간단히 구현할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;

int S[12];
bool visited[12];
vector<int> comb;
vector<int>::iterator iter;

void func(int x, int y) {
    if (comb.size() == 6) {
        for (iter = comb.begin();iter != comb.end();iter++) {
            cout << S[*iter] << ' ';
        }
        cout << '\n';
    }
    else {
        for (int i = y;i < x;i++) {
            if (!visited[i]) {
                visited[i] = true;
                comb.push_back(i);
                func(x,i+1);
                comb.pop_back();
                visited[i] = false;
            }
        }
    }
}

int main()
{
    int x;
    cin >> x;
    int y;
    while (x != 0) {
        for (int i = 0;i < x;i++) {
            cin >> y;
            S[i] = y;
        }
        func(x,0);
        cout << '\n';
        cin >> x;
    }
}