백준 6603 로또

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

6603번: 로또

행운의 숫자를 K(K>6)개 고른 후, 그 중에서 6개의 숫자를 고르는 문제다.

bitset이 깔끔할 것이라 생각했지만, 오늘은 재귀 공부하는 날이다.

 

숫자를 하나씩 추가하거나 제거하면서 조합을 만든다.

bool visited 배열을 통해 특정 숫자의 포함 여부를 판단할 수 있다.

#include <iostream>
using namespace std;

#include <vector>

bool visited[50]; // 방문 구분
void recur(int idx, int depth, const vector<int>& v){
    if(depth == 6){
        for(int i=1; i < 50; i++){
            if(visited[i]) cout << i <<' ';
        }cout <<'\n';
    }else{
        for(int i= idx+1; i<v.size(); i++){
            int now = v[i];
            if(visited[now]) continue;
            visited[now] = true;
            recur(i, depth+1, v);
            visited[now] = false;
        }
    }
}

int main(){
    while(1){
        int N; cin >> N;
        if(N == 0) break;
//
        //visited 초기화
        for(int i=0; i < 50; i++) visited[i] = false;
        //행운의 숫자 선택
        vector<int>v(N);
        for(int i=0; i < N; i++) cin >> v[i];
        //숫자모음 고고
        recur(-1, 0, v);
//
        cout <<'\n';
    }
    return 0;
}

recur 함수에서 특정 숫자의 포함 여부를 판단하는 과정에서 1부터 49까지 전부 조사한다.

 

vector는 stack처럼 이용할 수 있으며(push_back, pop_back) + 인덱스로 데이터 접근이 가능하다(O(1)).

#include <iostream>
using namespace std;

#include <vector>

vector<int> visit;
void recur(int idx, int depth, const vector<int>& v){
    if(depth == 6){
        for(auto i : visit){
            cout << i << ' ';
        }cout <<'\n';
    }else{
        for(int i= idx+1; i<v.size(); i++){
            int now = v[i];
            visit.push_back(now);
            recur(i, depth+1, v);
            visit.pop_back();
        }
    }
}

int main(){
    while(1){
        int N; cin >> N;
        if(N == 0) break;
//
        //행운의 숫자 선택
        vector<int>v(N);
        for(int i=0; i < N; i++) cin >> v[i];
        //숫자모음 고고
        recur(-1, 0, v);
//
        cout <<'\n';
    }
    return 0;
}