(c++)백준 16637번: 괄호 추가하기

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

[풀이]

dfs를 이용하여 풀 수 있는 문제였다.

괄호를 묶을 수 있는지 확인하는 것이 필요하다.

1. 괄호 묶을 수 있는지 확인(남은 개수 확인)

2. 현재까지 계산한 값과 다음 값 사이의 연산자 저장

3. 괄호를 묶는 경우. 괄호 묶은 연산자 계산하고 이전까지의 값과 계산

4. 괄호를 묶지 않는 경우. 현재 위치의 값과 이전까지의 값 계산

※Max값 초기화할 때 습관적으로 -1 했다가 "틀렸습니다." 나옴, climits 라이브러리의 INT_MIN으로 초기화해주기!!

 

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;

int N;
string s;
int Max = INT_MIN;

int getResult(int x, int y, int op) {
	if (op == '+') {
		return x + y;
	}
	else if (op == '-') {
		return x - y;
	}
	else if (op == '*') {
		return x * y;
	}
}

void dfs(int idx, int num) {
	char op;
	//마지막 연산자까지 봤을 때
	if (idx > N - 1) {
		Max = max(Max, num);
		return;
	}
	//지금까지 계산한 값과 현재 위치 사이의 연산자 확인
	if (idx == 0) {
		op = '+';
	}
	else
		op = s[idx - 1];
	//괄호로 묶는 경우
	if (idx + 2 < N) {
		//현재까지 값과 괄호로 묶은 값 사이 연산자로 계산
		int New = getResult(s[idx] - '0', s[idx + 2] - '0', s[idx + 1]);
		dfs(idx + 4, getResult(num, New, op));
	}
	//괄호로 묶지 않는 경우
	dfs(idx + 2, getResult(num, s[idx] - '0', op));
}

void solution() {
	cin >> N >> s;
	dfs(0, 0);
	cout << Max << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	solution();
	return 0;
}