백준[6603] - 로또

문제

백준 6603 문제 보기

접근 방법

숫자가 주어지면 중복없이 6자리 숫자를 만들고 출력하면 된다.
ans 배열에 선택한 숫자를 저장한다. 숫자를 선택할때는 다음과 같은 규칙을 따른다.

• ans의 첫번째 숫자는 모든 숫자의 범위에서 선택한다.
• ans의 두번째 숫자는 이전 선택한 수 보다 +1한 범위에서 숫자를 선택한다.
  (ex. 숫자가 1 ~ 10까지 주어졌을때 첫번째 숫자로 3을 선택했다면 두번째 선택할 숫자의 범위를 4 ~ 10으로 한정한다.)
• 이후 3번째 숫자를 선택할때는 규칙 2를 반복한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int K;
int ans[6];
vector<int> v;

// depth: 숫자의 길이, num: 선택할 숫자
void dfs(int depth, int num) {
    // 6자리면 출력
    if(depth == 6) {
        for(int i = 0; i < 6; i ++) {
            cout << ans[i] <<  " ";
        }
        cout << '\n';
        return;
    }

    for(int start = num; start < K; start ++) {
        ans[depth] = v[start];
        dfs(depth + 1, start + 1);
        ans[depth] = -1;
    }
}

int main() {
    while(1) {
        cin >> K;
        v.clear();

        // 0이면 종료
        if(K == 0)
            break;

        for(int i = 0; i < K ; i ++) {
            int num;
            cin >> num;
            // 숫자를 모두 벡터에 저장
            v.push_back(num);
        }

        dfs(0, 0);
        cout << '\n';
    }
    return 0;
}