이번에는 백준 16637번 괄호 추가하기 문제를 풀어보았습니다.
처음에는 일반적인 사칙연산 문제처럼 연산자 우선순위를 적용하려고 했지만, 문제를 다시 읽어보니 모든 연산자의 우선순위가 동일하고 왼쪽부터 순서대로 계산해야 했습니다.
또한 괄호는 연산자 하나만 포함할 수 있기 때문에, 특정 연산을 먼저 계산할지 말지만 결정하면 되는 문제라고 생각했습니다.
그래서 현재 위치에서 괄호를 사용하지 않는 경우와 사용하는 경우를 나누는 방식으로 구현하였습니다.
문제 설명
수식은 숫자와 연산자로 이루어져 있습니다.
모든 연산자는 우선순위가 동일하며, 왼쪽에서부터 차례대로 계산합니다.
괄호를 추가하면 괄호 안의 연산을 먼저 수행할 수 있습니다.
단, 괄호 안에는 연산자가 하나만 들어갈 수 있으며 중첩된 괄호는 사용할 수 없습니다.
괄호를 적절히 추가하여 만들 수 있는 식의 결과 중 최댓값을 구하는 문제입니다.
풀이 아이디어
연산자 우선순위를 고려하는 문제가 아니라 현재 연산을 어떤 순서로 수행할지를 결정하는 문제였습니다.
현재 위치를 기준으로 두 가지 경우를 생각하였습니다.
a op b op c- 현재 연산을 먼저 수행하는 경우
(a op b) op c- 뒤 연산을 괄호로 먼저 수행하는 경우
a op (b op c)재귀 함수에서는 이 두 경우를 모두 탐색하도록 구현하였습니다.
모든 연산을 수행한 경우 현재 계산된 값으로 최댓값을 갱신하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
string inp_string;
vector<char> operators;
vector<int> num;
int max_num = INT_MIN;
int calculate(char op, int a, int b) {
if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else {
return a * b;
}
}
void solve(int idx, int cur_num) {
if (idx == num.size()-1) {
max_num = max(max_num, cur_num);
return;
}
solve(idx+1, calculate(operators[idx], cur_num, num[idx+1]));
if (idx + 2 <= num.size()-1) {
int temp = calculate(operators[idx+1], num[idx+1], num[idx+2]);
solve(idx+2, calculate(operators[idx], cur_num, temp));
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
cin >> inp_string;
for (int i = 0; i < N; i++) {
if (i%2 == 0) {
num.push_back(inp_string[i] - '0');
} else {
operators.push_back(inp_string[i]);
}
}
solve(0,num[0]);
cout << max_num << endl;
return 0;
}풀이 흐름
- 입력받은 문자열에서 숫자와 연산자를 분리하여 저장합니다.
- solve 함수를 이용하여 현재 위치부터 가능한 모든 경우를 탐색합니다.
- 현재 연산을 먼저 수행하는 경우를 탐색합니다.
- 뒤 연산을 괄호로 먼저 계산하는 경우를 탐색합니다.
- 모든 숫자를 처리한 경우 최댓값을 갱신합니다.
- 모든 경우를 탐색한 뒤 최종 최댓값을 출력합니다.
구현 포인트
1. 숫자와 연산자 분리
입력 문자열에서 숫자와 연산자를 각각 따로 저장하였습니다.
for (int i = 0; i < N; i++) {
if (i%2 == 0) {
num.push_back(inp_string[i] - '0');
} else {
operators.push_back(inp_string[i]);
}
}이후 계산 과정에서는 숫자와 연산자를 인덱스로 접근할 수 있도록 하였습니다.
2. 연산 함수 구현
현재 연산자를 기준으로 실제 계산을 수행하는 함수를 만들었습니다.
int calculate(char op, int a, int b)연산자 종류에 따라 덧셈, 뺄셈, 곱셈을 수행하도록 구현하였습니다.
if (op == '+') {
return a + b;
} else if (op == '-') {
return a - b;
} else {
return a * b;
}3. 괄호를 사용하지 않는 경우
현재 연산을 먼저 수행하는 경우입니다.
solve(idx+1, calculate(operators[idx], cur_num, num[idx+1]));현재까지 계산된 값과 다음 숫자를 연산한 뒤 다음 위치로 이동합니다.
예를 들어
a op b op c에서
(a op b)를 먼저 수행하는 경우입니다.
4. 괄호를 사용하는 경우
다음 연산을 괄호로 먼저 계산하는 경우입니다.
int temp = calculate(operators[idx+1], num[idx+1], num[idx+2]);먼저
(b op c)를 계산합니다.
이후 현재 값과 다시 계산합니다.
solve(idx+2, calculate(operators[idx], cur_num, temp));예를 들어
a op b op c에서
a op (b op c)를 수행하는 경우입니다.
5. 모든 숫자를 사용한 경우 최댓값 갱신
더 이상 계산할 숫자가 없는 경우 현재 값을 이용하여 최댓값을 갱신하였습니다.
if (idx == num.size()-1) {
max_num = max(max_num, cur_num);
return;
}모든 괄호 배치를 탐색한 뒤 가장 큰 값을 정답으로 사용하였습니다.
