백준 6603 로또 (재귀)

이전에 풀었던 로또 문제를 재귀로 푸는 것이다.

이전에는 순열로 풀기위해 선택한 번호는 0으로 넣고, 선택하지 않은 번호는 1로 넣는 새로운 vector를 선언해주었다.

하지만 재귀에서는 앞선 암호 문제처럼 재귀를 통해 넣고, 안 넣고를 할 수 있기 때문에 새로운 vector가 필요없다.

대신 넣고 안 넣고를 check할 check 배열을 하나 생성한다.

 

check 배열을 놓고 풀지 않고, vector하나를 두고 선택하면 vector에 push_back으로 넣고, 넣지 않으면 pop_back으로 빼서 풀 수도 있다. 

 

자세한 설명은 아래 주석으로..

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
//선택되면 true로 설정된다.
bool check[50];
 
void solve(int idx, int cnt, vector<int> v, int k) {
    //6개를 선택하고 나면 더이상 선택하지 않도록 한다.
    if (cnt > 6)return;
    //6개를 선택하면 check에 true로 저장된 index 번호로 v에서 출력한다.
    if (cnt == 6) {
        for (int i = 1; i < 50; i++) {
            if (check[i]) printf("%d ", i);
        }
        printf("\n");
        //정답 출력하고 나서 return 하는 거 까먹지 말기
        return;
    }
    //만약 주어진 k보다 idx가 커지면 return
    if (idx >= k)return;
 
    //선택하는 경우이기 때문에 값을 check하고(선택하고) 나서 solve에 들어간다.
    check[v[idx]] = true;//배열의 index로 배열의 value를 사용하는 것에 주의
    solve(idx + 1, cnt + 1, v, k);
    //선택하지 않는 경우이기 때문에 값을 false로 하고 나서 solve에 들어간다.
    check[v[idx]] = false;
    solve(idx + 1, cnt, v, k);
}
 
int main(int argc, char** argv) {
    
    while (1) {
        int k;
        cin >> k;
 
        if (k == 0)break;
        
        vector<int> v(k);
        for (int i = 0; i < k; i++)cin >> v[i];
 
        //매 test case에 들어가기 전에 초기화 해줘야 한다.
        for (int i = 1; i < 50; i++) check[i] = false;
        //현재 선택 할 index번호, 선택된 개수, 번호가 들어 있는 vector
        solve(0, 0, v, k);
        printf("\n");
    }
    
 
    return 0;
}