#6603 로또 (C++)

링크 : www.acmicpc.net/problem/6603

6603번: 로또

전형적인 백트레킹 문제. 

해당 문제는 주어진 값의 범위와, 로또의 당첨 숫자는 6개를 기억하면 문제없이 풀 수있다.

 

* 2021/1/23 코드 수정

Memset과 배열을 활용한 풀이

#include <iostream>
#include <cstring>
using namespace std;
bool ch[50] = {false,};
int n=0,temp=0,arr[14];

void dfs(int num, int cnt){
    if(num>n){
        if(cnt==6){
            for(int i=1; i<=n; i++){
                if(ch[arr[i]]) cout << arr[i] << " ";
            }
            cout << "\n";
        }
        else return;
    }
    else{
        ch[arr[num]] = true;
        dfs(num+1,cnt+1);
        ch[arr[num]] = false;
        dfs(num+1,cnt);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    while(cin >> n){
        if(n==0) break;
        for(int i=1; i<=n; i++) cin >> arr[i];
        dfs(1,0);
        memset(ch,false,sizeof(ch));
        cout << "\n";
    }
   return 0;
}

 

Vector를 활용한 풀이

#include <iostream>
#include <vector>
using namespace std;

vector<int> lotto;

void solve(vector<int> &a, int index, int cnt){
    if(cnt==6){
        for(int num:lotto) cout << num << " ";
        cout << "\n";
        return;
    }
    int n = a.size();
    if(n==index) return;
    lotto.push_back(a[index]);
    solve(a,index+1,cnt+1);
    lotto.pop_back();
    solve(a,index+1,cnt);
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n=0;
    while(cin>>n){
        if(n==0) break;
        vector<int> a(n);
        for(int i=0; i<n; i++) cin >> a[i];
        solve(a,0,0);
        cout << "\n";
    }
   return 0;
}