Koala - 7기/코딩테스트 준비 스터디

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

마누카 2022. 7. 6. 18:34

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

 

6603번: 로또

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로

www.acmicpc.net

 

문제분석

  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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}
 cs

문제풀이

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

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