이번에는 백준 14888번 연산자 끼워넣기 문제를 풀어보았습니다.
주어진 숫자의 순서는 변경할 수 없고, 숫자 사이에 들어갈 연산자의 순서만 결정하면 됩니다.
각 단계에서 사용할 수 있는 연산자를 하나씩 선택하여 계산을 진행하고, 모든 경우를 DFS로 탐색하는 방식으로 구현하였습니다.
문제 설명
N개의 숫자와 N-1개의 연산자가 주어집니다.
연산자는 다음 네 종류입니다.
- 덧셈
+ - 뺄셈
- - 곱셈
* - 나눗셈
/
숫자의 순서는 변경할 수 없으며, 연산자 우선순위도 적용하지 않고 앞에서부터 순서대로 계산합니다.
가능한 모든 연산자 배치를 확인한 뒤 결과의 최댓값과 최솟값을 구하는 문제입니다.
풀이 아이디어
현재까지 계산한 값과 다음 숫자를 이용해 연산을 하나 수행합니다.
연산자는 다음과 같이 인덱스로 관리하였습니다.
0 : +
1 : -
2 : *
3 : /현재 사용할 연산자를 선택한 뒤 해당 연산자의 개수를 1 감소시키고, 다음 숫자에 대해 다시 DFS를 수행합니다.
재귀 호출이 끝난 뒤에는 사용했던 연산자의 개수를 다시 증가시켜 다른 경우에서도 사용할 수 있도록 복구하였습니다.
마지막 숫자까지 계산했다면 현재 결과를 이용하여 최댓값과 최솟값을 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int num[11];
int op[4];
int max_val = INT_MIN;
int min_val = INT_MAX;
int calculate(int a, int b, int oper) {
if (oper == 0) {
return a + b;
} else if (oper == 1) {
return a - b;
} else if (oper == 2) {
return a * b;
} else {
return a / b;
}
return 0;
}
void dfs(int oper, int index, int ret_num) {
ret_num = calculate(ret_num, num[index], oper);
op[oper]--;
for (int i=0; i<4; i++) {
if (op[i] == 0) continue;
dfs(i, index+1, ret_num);
}
op[oper]++;
if (index == N-1) {
max_val = max(ret_num, max_val);
min_val = min(ret_num, min_val);
return;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
cin >> num[i];
}
for (int i=0; i<4; i++) {
cin >> op[i];
}
for (int i=0; i<4; i++) {
if (op[i] == 0) continue;
dfs(i, 1, num[0]);
}
cout << max_val << '\n' << min_val;
return 0;
}풀이 흐름
-
N개의 숫자를 입력받습니다.
-
+,-,*,/연산자의 개수를 입력받습니다. -
첫 번째 숫자를 현재 계산값으로 설정합니다.
-
사용할 수 있는 연산자 중 하나를 선택합니다.
-
현재 계산값과 다음 숫자를 선택한 연산자로 계산합니다.
-
사용한 연산자의 개수를 1 감소시킵니다.
-
남아 있는 연산자에 대해 다음 DFS를 수행합니다.
-
재귀 호출이 끝난 뒤 사용했던 연산자의 개수를 복구합니다.
-
마지막 숫자까지 계산했다면 최댓값과 최솟값을 갱신합니다.
-
모든 연산자 배치를 확인한 뒤 결과를 출력합니다.
구현 포인트
1. 연산자 개수 관리
int op[4];연산자 종류별로 남은 개수를 저장하였습니다.
각 인덱스는 다음과 같습니다.
op[0] : +
op[1] : -
op[2] : *
op[3] : /입력도 같은 순서로 주어지기 때문에 그대로 저장하였습니다.
2. 연산 함수 분리
int calculate(int a, int b, int oper)선택된 연산자의 종류에 따라 실제 계산을 수행하도록 하였습니다.
if (oper == 0) {
return a + b;
} else if (oper == 1) {
return a - b;
} else if (oper == 2) {
return a * b;
} else {
return a / b;
}현재까지 계산된 값 a와 다음 숫자 b를 이용하여 결과를 반환합니다.
3. DFS에서 현재 연산 수행
ret_num = calculate(ret_num, num[index], oper);현재까지 계산한 값 ret_num과 index번째 숫자를 이용하여 선택한 연산을 수행합니다.
예를 들어
현재 값 = 10
다음 숫자 = 3
연산자 = -라면
10 - 3 = 7이 되고, 이후 재귀에서는 7을 현재 값으로 사용하게 됩니다.
4. 사용한 연산자 개수 감소
op[oper]--;현재 연산자를 하나 사용했으므로 해당 연산자의 개수를 1 감소시킵니다.
이후에는 아직 남아 있는 연산자만 사용할 수 있습니다.
for (int i=0; i<4; i++) {
if (op[i] == 0) continue;
dfs(i, index+1, ret_num);
}개수가 0인 연산자는 더 이상 선택할 수 없으므로 건너뜁니다.
5. 백트래킹
현재 연산자를 사용한 모든 경우의 탐색이 끝나면 다시 연산자 개수를 복구합니다.
op[oper]++;예를 들어 덧셈 하나를 사용한 뒤 해당 경우의 탐색이 끝났다면, 다른 연산자 배치를 확인할 때는 다시 덧셈을 사용할 수 있어야 합니다.
따라서
연산자 선택
→ 개수 감소
→ 재귀 탐색
→ 개수 복구방식으로 백트래킹을 수행하였습니다.
6. 첫 번째 숫자부터 계산 시작
dfs(i, 1, num[0]);첫 번째 숫자 num[0]은 연산 없이 그대로 시작값으로 사용합니다.
index는 1부터 시작하여 두 번째 숫자부터 연산을 적용합니다.
즉, 첫 번째 DFS 호출에서는
num[0] (연산자) num[1]을 계산하게 됩니다.
7. 첫 번째 연산자 선택
for (int i=0; i<4; i++) {
if (op[i] == 0) continue;
dfs(i, 1, num[0]);
}처음 숫자와 두 번째 숫자 사이에 들어갈 연산자를 네 종류 중 하나 선택합니다.
해당 연산자의 개수가 0이라면 사용할 수 없으므로 넘어갑니다.
이후 DFS 내부에서 나머지 연산자들을 계속 선택하게 됩니다.
8. 마지막 숫자까지 계산한 경우
if (index == N-1) {
max_val = max(ret_num, max_val);
min_val = min(ret_num, min_val);
return;
}index == N-1이면 마지막 숫자까지 계산한 상태입니다.
하나의 완성된 연산자 배치에 대한 결과가 만들어졌으므로 현재 결과를 최댓값, 최솟값과 비교하여 갱신합니다.
9. DFS와 백트래킹
이 문제에서는 각 숫자 사이에 어떤 연산자를 넣을지 모든 경우를 확인해야 합니다.
따라서 DFS를 이용한 완전탐색으로 해결할 수 있습니다.
또한 연산자를 사용한 뒤
op[oper]--;재귀 탐색이 끝나면
op[oper]++;로 다시 복구하므로 백트래킹도 함께 사용한 풀이입니다.
10. 시간복잡도
총 N-1개의 연산자를 배치해야 합니다.
연산자의 종류는 최대 4개이고, 각 단계마다 남아 있는 연산자 중 하나를 선택합니다.
N은 최대 11이므로 가능한 모든 연산자 배치를 DFS로 탐색해도 충분히 해결할 수 있습니다.
최악의 경우를 단순하게 보면
O(4^(N-1))정도로 볼 수 있지만, 실제로는 각 연산자의 개수가 정해져 있기 때문에 탐색하는 경우의 수는 이보다 적습니다.
