[백준] 로또

https://www.acmicpc.net/problem/6603

6603번: 로또

우선 문제부터 간단하게 요약하면, 

 

k 값과 k개의 숫자가 주어지면 여기에서 6개를 뽑는 가짓수를 사전순으로 출력해야 하는 문제입니다.

 

<Solution>

기본적인 combination문제이므로 뽑거나 뽑지 않거나를 dfs를 사용하여 구현하면 됩니다.

 

아래의 풀이에서 추가해도 되는 부분은, 만약 남은 것들을 모두 뽑아도 6개를 뽑지 못하는 경우 더이상 상태 발전을 하지 않도록 구현이 가능할 듯 합니다. 하지만 이 부분을 넣지 않아도 충분히 통과 할 수 있으므로, 넣지 않은 구현은 아래와 같습니다. 

(사전순 정렬은 처음 input을 사전순으로 받고, 고르는 것이 먼저 진행되므로 자연스럽게 정렬하지 않아도 사전순으로 출력됩니다.)

#include <iostream>
#include <vector>

using namespace std;

vector<int> lottoAns;
int k;

void solve(int *arrayPtr, int index, int curCnt){
    // when will it end
    if(curCnt == 6){
        for(auto& k:lottoAns){
            cout << k << ' ';
        }
        cout << '\n';
        return;
    }
    if(index == k) return; // out of range
    // select
    lottoAns.push_back(*(arrayPtr+index));
    solve(arrayPtr, index+1, curCnt+1);
    lottoAns.pop_back();
    // doesn't select
    solve(arrayPtr, index+1, curCnt);
    // since lottoAns always empty we don't have to initialize it every time
}

int main(){
    
    while(1){
        cin >> k;
        if(!k) break;

        int kArray[15];
        for(int i = 0; i<k; i++){
            cin >> kArray[i];
        }
        solve(kArray, 0, 0);
        cout << '\n';
    }
    return 0;
}