공부 자료/알고리즘
(C/C++) 백준 6603번 - 로또
뚜루뚜루세니
2021. 7. 19. 11:43
728x90
문제 출처: https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
1. 코드
|
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
|
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int k;
int arr[13];
int ans[13];
void Lotto(int idx, int cnt) {
if (cnt == 6) {
for (int i = 0; i < 6; i++) {
printf("%d ",ans[i]);
}
printf("\n");
return;
}
for (int i = idx; i < k; i++) { //arr 0부터 k-1까지 탐색
ans[cnt] = arr[i]; //0~5번째 깊이까지 새로 탐색 숫자를 넣음.
Lotto(i + 1, cnt + 1); //재귀. 하나의 깊이를 탐색 후 저장-> 다음 함수호출 시 카운트 하나 더 해줘야함
}
}
int main() {
while (1) {
scanf("%d", &k);
if (k == 0) //0입력 받으면 멈춤
break;
for (int i = 0; i < k; i++) {
scanf("%d", &arr[i]);
}
Lotto(0, 0);
printf("\n");
}
return 0;
}
|
cs |
2. 해결 방법
원소는 처음부터 오름차순으로 주어지기 때문에 sort과정은 필요 X
6개의 원소로 이루어진 배열 조합을 원하기 때문에 cnt == 6이면 배열을 출력하고 함수를 종료 하게 해줬다.
처음에 숫자를 입력받고, 0을 입력 받으면 멈추고, 아니라면 배열 arr에 하나씩 수를 입력받는다.
그 다음에 arr배열을 0부터 k-1까지 탐색하면서 재귀를 이용하여 새롭게 탐색한 숫자를 ans배열에 넣어준다.
하나의 깊이를 탐색한 후에 ans배열에 값을 저장해줬기 때문에 다음 함수를 호출할 때는 카운트 값을 하나 증가시켜줘야한다. 카운트가 6이 안되는 재귀함수들은 계속해서 lotto를 호출 -> 결국 카운트 값이 6인 배열만 출력한다.
3 느낀점
처음에 오름차순으로 정렬를 하지 않아도 된다는 조건을 살피지 못해서 헤맸다. 문제를 더 꼼꼼하게 읽어야겠다.
728x90