백준 - 16637 괄호 추가하기

문제

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

16637번: 괄호 추가하기

왼쪽부터 계산하는 수식에 괄호를 추가해 식의 최댓값을 구하는 문제였다.

 

문제 풀이

처음에 이 문제를 굳이 그리디로 풀려고 시도하다가 조건이 너무 많아져서 실패했다. 그냥 dfs로 푸니까 쉽게 해결됐다..

 

dfs를 할 때, 다음 연산을 바로 하는 경우와 다음 숫자와 다다음 숫자가 다다음 연산을 먼저 하는 경우로 나뉘게 하면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> nums;
vector<char> opers;
long long maxResult = -987654321;

long long operResult(long long result, int nextNum, char nextOper) {
	if (nextOper == '+') {
		return result + nextNum;
	}
	else if (nextOper == '*') {
		return result * nextNum;
	}
	else if (nextOper == '-') {
		return result - nextNum;
	}
}

void dfs(long long result, int index) {
	//printf("index: %d result: %lld\n", index, result);
	if (index >= nums.size()-1) {
		maxResult = max(maxResult, result);
		//printf("\n");
		return;
	}

	int nextNum = nums[index+1];
	char nextOper = opers[index+1];

	dfs(operResult(result, nextNum, nextOper), index + 1);

	if (index + 2 <= nums.size() - 1) {
		//printf("괄호 사용 result: %lld\n", result);
		int nenextNum = nums[index + 2];
		char nenextOper = opers[index + 2];
		//printf("nextNum: %d nextOper: %c nenextNum: %d nenextOper: %c\n", nextNum, nextOper, nenextNum, nenextOper);
		dfs(operResult(result, operResult(nextNum, nenextNum, nenextOper), nextOper), index + 2);
	}
}

int main(int argc, char** argv)
{
	int N;

	scanf("%d", &N);

	char a;
	long long result;



	for (int i = 0; i <= N; i++) {
		scanf("%c", &a);
		if (a >= '0' && a <= '9') { //숫자
			nums.push_back(a - '0');
		}
		else {
			opers.push_back(a);
		}
	}

	dfs(nums[0], 0);

	printf("%lld", maxResult);

}