[Java] 백준(실버-1) 14888번 - 연산자 끼워넣기
문제 풀이
이 문제는 재귀를 통한 백트래킹 유형으로 풀 수 있는 문제이다.
아이디어 도출
문제의 입력을 살펴보면 다음과 같다.
1
2
3
첫째 줄 : 수의 개수 N
둘째 줄 : 수
셋째 줄 : 덧셈, 뺄셈, 곱셈, 나눗셈 각각의 개수
필자는 연산자를 입력받는 셋째 줄에서 각 연산자를 1차원 배열로 처리하도록 구현하였다. 문제풀이를 위한 아이디어는 다음과 같다.
- N개의 수를 N 크기의 배열에 입력받고, 4칸의 배열에 연산자의 개수를 입력받는다.
- 연산자 개수만큼 4번을 반복하며 +, -, *, / 경우에 따른 DFS 재귀함수를 호출해나간다.
- 첫번째 수부터 N번째 수까지 +, -, *, / 연산한 값을 깊이를 1 증가시키며 다음 DFS로 재귀 호출한다.
- 이때, 연산자 개수를 1씩 감소시키고 DFS를 호출한 뒤 연산자 개수를 다시 1 증가시켜줘야 한다.
- 재귀의 깊이가 N과 같다면 모든 수를 탐색하며 연산자 개수를 사용했으니 이때의 연산 값이 최대값인지 최솟값인지 갱신해주고 재귀를 종료한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
import java.io.*;
import java.util.*;
class Main {
// 둘째줄에 N개의 수를 담을 배열 선언
static int[] arr;
// +,-,*,/ 4개의 연산자 개수를 담을 배열 선언
static int[] operator;
// 수의 개수 N, 최댓값 max, 최솟값 min 선언
static int N, max, min;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
N = Integer.parseInt(br.readLine());
// 수 배열 및 연산자 배열 초기화
arr = new int[N];
operator = new int[4];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0; i<4; i++) {
operator[i] = Integer.parseInt(st.nextToken());
}
// 최댓값 및 최솟값을 찾기 위한 초기화
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
// DFS 함수 호출
dfs(arr[0], 1);
bw.write(max+"\n");
bw.write(min+"\n");
}
}
public static void dfs(int n, int idx) {
/**
* 재귀 종료 조건
* 1부터 N 수까지의 탐색을 완료했다면 재귀를 종료한다.
* 이때, 현재 수와 재귀호출을 통해 만들어낸 n이 최대일 때와 최소인 값을 담은 후 종료한다.
*/
if(idx == N) {
max = Math.max(max, n);
min = Math.min(min, n);
return;
}
for(int i=0; i<4; i++) {
// 현재 연산자 개수가 1개 이상이라면
if(operator[i] > 0) {
// 해당 연산자 개수 1 차감
operator[i]--;
/*
* i 별로 재귀호출한다.
* i==0 이면 +
* i==1 이면 -
* i==2 이면 *
* i==3 이면 /
*/
if(i == 0) {
dfs(n + arr[idx], idx+1);
} else if(i == 1) {
dfs(n - arr[idx], idx+1);
} else if(i == 2) {
dfs(n * arr[idx], idx+1);
} else if(i == 3) {
dfs(n / arr[idx], idx+1);
}
// 해당 연산자 개수를 다시 원복한다.
operator[i]++;
}
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.