[백준 / C++] 16637번: 괄호 추가하기 (삼성 A형 기출)

https://www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

난이도: solved.ac 골드 3

 

알고리즘 분류

구현, 브루트포스 알고리즘

 

접근 방법 및 구현

괄호는 한 번에 최대 두 개의 숫자만 묶을 수 있으므로 괄호는 s[i]와 s[i+2]를 묶는다.

s[i+2]가 문자열 크기를 벗어나지 않으면 괄호를 만들어 계산한다.

 

만든 괄호 안을 먼저 계산한 후, 지금까지 계산했던 결과와 함께 s[i-1]에 있는 연산자를 통해 계산한다.

 

괄호를 만들어 계산했다면 다음 index는 현재 index에서 +4가 된다.

 

계산하는 함수를 재귀로 호출해 괄호를 만드는 경우를 모두 계산하면, 다시 돌아와 s[i]를 s[i+2]와 묶지 않고 계산을 한다.

 

이전까지 계산했던 결과와 s[i]를 s[i-1] 연산자로 계산해 index를 +2 시켜 다시 재귀함수를 호출한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int N, ans = INT_MIN;
string s;
void cal(int cur, int res);
// cur은 s에서 현재 가리키는 index를 의미
// cur + 2 < N이면 s[cur]를 기점으로 하는 괄호를 만들 수 있음
// 1) s[cur]를 기점으로 괄호를 만들 수 있다면 먼저 괄호를 만들어 계산
// 2) 그 후 s[cur]를 괄호에 포함하지 않는 경우로 계산
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> s;
	cal(0, 0);
	cout << ans;
}
 
void cal(int cur, int res) {
	if (cur > N) {
		if (res > ans)
			ans = res;
		return;
	}
	if (cur + 2 < N) {
		// 괄호를 만들 수 있을 때
		int tmp1, tmp2, tres;
		// tmp1: 만들 괄호 안에서 첫 번째 수
		// tmp2: 만들 괄호 안에서 두 번째 수
		// tres: 괄호를 계산한 결과
		tmp1 = (s[cur] - '0');
		tmp2 = (s[cur + 2] - '0');
		if (s[cur + 1] == '+')
			tres = tmp1 + tmp2;
		else if (s[cur + 1] == '-')
			tres = tmp1 - tmp2;
		else if (s[cur + 1] == '*')
			tres = tmp1 * tmp2;
		if (cur == 0)
			cal(4, tres);	// cur = 0이면 s[cur]앞에 아무 연산자도 없으므로
		else {
			// cur > 0일 때
			if (s[cur - 1] == '+')
				cal(cur + 4, res + tres);
			else if (s[cur - 1] == '-')
				cal(cur + 4, res - tres);
			else if (s[cur - 1] == '*')
				cal(cur + 4, res * tres);
		}	
	}
	// 괄호를 만들지 않는 경우
	int num = s[cur] - '0';
	if (cur == 0)
		cal(2, num);
	else {
		if (s[cur - 1] == '+')
			cal(cur + 2, res + num);
		else if (s[cur - 1] == '-')
			cal(cur + 2, res - num);
		else if (s[cur - 1] == '*')
			cal(cur + 2, res * num);
	}
}

 

성능

코드 제출 결과