3040번: 백설 공주와 일곱 난쟁이
매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.
www.acmicpc.net
부르트포스 방식으로 9개 중 7개를 뽑는 과정에서 7개의 합이 100이 되면 뽑은 수들을 출력하면 되는 문제입니다.
9개중 7개를 뽑는다고 명시가 되어있으니 조합으로 해결해야하고, 7개를 뽑았을 때 합이 100인 수들을 출력하면 됩니다.
7개를 뽑았으나 합이 100이 아닌경우에 그냥 리턴을 시켜주시면 되고, 재귀를 돌릴때 다음 매개변수 sum이 100보다 크면 continue를 해서 시간단축을 하였습니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static ArrayList<Integer> ans = new ArrayList<>();
static int list[] = new int[9];
static void func(int idx, int cnt, int sum) {
if (cnt == 7) {
if (sum != 100)
return;
for (int i = 0; i < 7; i++) {
sb.append(ans.get(i) + "\n");
}
sb.append("\n");
return;
}
for (int i = idx; i < 9; i++) {
if (sum + list[i] > 100)
continue;
ans.add(list[i]);
func(i + 1, cnt + 1, sum + list[i]);
ans.remove(cnt);
}
}
static void input() throws Exception {
for (int i = 0; i < 9; i++) {
st = new StringTokenizer(br.readLine());
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func(0, 0, 0);
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > Bruteforce' 카테고리의 다른 글
| boj 14456 Hoof, Paper, Scissors (Bronze) (0) | 2022.12.30 |
|---|---|
| boj 17281 ⚾ (0) | 2021.02.16 |
| boj 2961 도영이가 만든 맛있는 음식 (0) | 2021.02.15 |
| boj 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (0) | 2021.01.29 |
| boj 1018 체스판 다시 칠하기 (0) | 2021.01.29 |