[백준/C++] 6603번 로또

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

6603번: 로또

 

문제분석

1. 분류
   • 조합, 백트렉킹, DFS
2. 문제설명
   • 로또번호를 출력하는 프로그램이다.
   • N을 입력받고, 크기가 N인 배열에 1~49 숫자를 중복없이 입력한다.
   • 해당 숫자를 조합하여 6개의 로또번호를 출력한다.
   • 0을 입력하면 종료된다.
   • 배열의 크기는 최소 7 - 최대 12이다.

 

입력

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

부연설명 

7 (배열의 크기)

1 2 3 4 5 6 7 (배열의 값)

0 (프로그램 종료)

 

출력

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

코드

#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int used[100];
int path[100];
 
void inputNum(vector<int> &lottery) {
    for (int x = 0; x < N; x++) {
        cin >> lottery[x];
    }
}
 
void getLotteryNum(vector<int> &lottery, int level, int start) {
 
    if (level == 6) {
        for (int x = 0; x < 6; x++) {
            cout << path[x] << " ";
        }
        cout << '\n';
        return;
    }
 
    for (int x = start; x < N; x++) {
        if (used[x] == 1)continue;
        used[x] = 1;
        path[level] = lottery[x];
        getLotteryNum(lottery, level + 1, x + 1);
        used[x] = 0;
        path[level] = 0;
    }
}
 
int main() {
    while (1) {
        cin >> N;
        if(N == 0 || N <= 6 || N >= 13) break;
 
        vector<int> lottery;
        lottery.assign(N, 0);
        inputNum(lottery);
 
        getLotteryNum(lottery, 0, 0);
        cout << '\n';
    }
 
    return 0;
}

문제풀이

arr[N] 입력 받고, 해당 수 중에 6가지 수의 조합을 출력하는 문제이다.

1. 반복문 조건
   • 배열의 크기는 최소 7, 최대 12이다. 해당 범위를 벗어나면 break.
   • 0을 입력하면 break.
2. dfs 조건
   • level은 6 (6가지 로또 번호)
   • branch는 N (입력받은 배열의 크기)
   • 조합으로 수를 출력한다.