[BOJ] 6603. 로또

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

6603번: 로또

 

K개 중 6개를 고르는 문제이다. 고르는 개수가 정해져 있기 때문에 넥퍼뮤를 사용해도 좋지만 조합을 이용해서 구했다.

 

먼저 k개만큼 배열에 입력받고, 이 배열에서 6개를 고르는 모든 경우를 구해준다.

숫자를 고를때마다 lotto 벡터에 넣어주고 6개의 숫자를 고른 경우 lotto 벡터에 있는 값들을 모두 출력해주고 return

k개의 숫자를 사용할지 안 할지 모두 정한 경우(index 가 k를 넘어간 경우)에도 더 이상 고를 숫자가 없으므로 return 해준다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int k;
int num[12];
 
void solve(int index, int select, vector<int> &lotto) {
    //고를 수의 범위가 넘어감
    if(index > k) {
        return;
    }
 
    //6개를 모두 골랐다
    if(select == 6) {
 
        //고른 숫자들을 모두 출력해준다.
        for(int i=0; i<6; i++) {
            cout << lotto[i] << ' ';
        }
        cout << '\n';
        return;
    }
 
 
    //현재 index번째 숫자를 고른 경우를 탐색.
    //하나를 골랐으므로 select 값을 1 증가시킨다.
    lotto.push_back(num[index]);
    solve(index+1, select+1, lotto);
 
    //다시 빼주고 고르지 않는 경우를 탐색
    lotto.pop_back();
    solve(index+1, select, lotto);
 
}
 
 
int main() {
 
    while(true) {
        cin >> k;
        if(k == 0) break;
 
        for(int i=0; i<k; i++) {
           int x;
           cin >> x;
           num[i] = x;
        }
 
        vector<int> lotto;
        solve(0,0,lotto);
        cout << '\n';
    
    }
 
    return 0;
}