반응형
🔺 문제
🔺 코드
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
51
52
53
54
55
56
57
58
59
60
61
|
import java.util.*;
import java.io.*;
public class Main {
public static int MAX = Integer.MIN_VALUE; // 최댓값
public static int MIN = Integer.MAX_VALUE; // 최솟값
public static int[] sign = new int[4]; // 부호
public static int[] num; // 숫자
public static int N; // 숫자 개수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 수 개수 받기
N = Integer.parseInt(br.readLine());
num = new int[N];
// 숫자 입력 받기
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i = 0 ; i < N ; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
// 연산자 받기
st = new StringTokenizer(br.readLine()," ");
for(int i = 0 ; i < 4 ; i++) {
sign[i] = Integer.parseInt(st.nextToken());
}
// 브루트포스 & 백트래킹
DFS(num[0], 1);
System.out.println(MAX);
System.out.println(MIN);
}
public static void DFS(int n, int idx) {
// 모든 연산자를 썼을 경우
if(idx == N) {
MAX = Math.max(MAX, n);
MIN = Math.min(MIN, n);
return;
}
for(int i = 0 ; i < 4 ; i++) {
// 연산자 개수가 1개 이상인 경우
if(sign[i] > 0) {
sign[i]--; // 해당 연산자 1 감소
switch(i) {
case 0: DFS(n + num[idx], idx + 1); break;
case 1: DFS(n - num[idx], idx + 1); break;
case 2: DFS(n * num[idx], idx + 1); break;
case 3: DFS(n / num[idx], idx + 1); break;
}
sign[i]++; // 재귀 호출 종료 시, 해당 연산자 개수 복구 (다른 경우의 수 탐색 위해 / 백트래킹)
}
}
}
}
|
cs |
✅ 해결 아이디어
✔ 브루트포스 & 백트래킹
- 연산 기호가 0이 될 때까지 재귀 돌려주기
- 연산하기 전 1 감소시키고, 연산 후 다시 돌려주기 (다른 경우의 수 탐색 위해 / 백트래킹)
💬 느낀 점
으앙 모르겠어서 다른 분 코드 보고 제출했다...
복습을 많이 해야겄다..
완전탐색.. 재귀.. 백트래킹.. DFS..
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 9.16 |
(참고)
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 14719번: 빗물 (0) | 2023.05.20 |
---|---|
[백준/JAVA] 2504번: 괄호의 값 (0) | 2023.05.20 |
[백준/JAVA] 1292번: 쉽게 푸는 문제 (1) | 2023.05.19 |
[백준/JAVA] 2693번: N번째 큰 수 (0) | 2023.05.19 |
[백준/JAVA] 2609번: 최대공약수와 최소공배수 (0) | 2023.05.19 |