Competition/Baekjoon
[백준] 6603번 자바 로또
bisi
2020. 4. 27. 03:19
문제 출처
https://www.acmicpc.net/problem/6603
6603번: 로또
문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2
www.acmicpc.net
접근 방식 및 풀이
- 백트래킹 방법, DFS 방법이 있었지만, DFS으로 구현하였다.
- DFS로 탐색하다가 6자리 문자열을 다 찾았으면 result가 true인 것들만 출력한다.
소스 코드
|
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
|
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static int N ;
static int[] arr;
static boolean[] result;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
while ( true){
N = sc.nextInt();
if(N==0){
break;
}
arr = new int[N];
result = new boolean[N];
for (int i = 0; i <N ; i++) {
arr[i] = sc.nextInt();
}
DFS(0, 0);
System.out.println();
}
}
private static void DFS(int start, int depth){
if(depth == 6){
for (int i = 0; i <N ; i++) {
if(result[i]){
System.out.print(arr[i] + " ");
}
}
System.out.println();
}
for (int i = start; i <N ; i++) {
result[i] = true;
DFS(i+1, depth+1);
// 출력하고 돌아올땐 다시 사용해야 하므로 false로
result[i] = false;
}
}
}
|
결과
