[C++] 백준 16637 - 괄호 추가하기

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

16637번: 괄호 추가하기

<풀이>

1. 수식을 입력받는다.

2. 괄호를 적절히 추가해서 얻을 수 있는 결과의 최대값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우의 수를 다 해보아야 합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 괄호 추가하기

=> 모든 숫자에서 괄호를 추가하는 경우와 안하는 경우로 나누어집니다. 3 + 8 * 7 - 9 * 2 를 예시로 들어보겠습니다. 8에서 괄호를 추가 안하는 경우는 전 숫자에 +8을 하고 다음 숫자 7로 넘어갑니다. 괄호를 추가하는 경우는 전 숫자에 +(8*7)을 하고 다음 숫자 9로 넘어갑니다. 위 방식이 반복적으로 일어나므로, 저는 재귀함수를 이용하여 구현하였습니다. 

 

#include <iostream>
#include <string.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
int N;
int nCnt, oCnt;
int num[11];
char oper[10];
int answer;
 
int calculate(int n1, int n2, char oper) {
    switch (oper) {
    case '+':
        return n1 + n2;
    case '-':
        return n1 - n2;
    case '*':
        return n1 * n2;
    }
}
 
int findMaxValue(int idx, int sum) {
 
    if (idx >= nCnt) {
        return sum;
    }
 
    int ret = INT_MIN;
    int nSum = 0;
 
    //괄호 X
    nSum = calculate(sum, num[idx], oper[idx - 1]);
    ret = max(ret, findMaxValue(idx + 1, nSum));
    //괄호 O
    if (idx + 1 < nCnt) {
        nSum = calculate(sum, calculate(num[idx], num[idx + 1], oper[idx]), oper[idx - 1]);
        ret = max(ret, findMaxValue(idx + 2, nSum));
    }
 
    return ret;
}
 
void solution() {
    answer = findMaxValue(1, 0);
}
 
int main() {
    //초기화
    N = 0;
    nCnt = 1, oCnt = 1;
    memset(num, 0, sizeof(num));
    memset(oper, '+', sizeof(oper)); //시작할때 '0 +'로 시작하기 위해
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (i % 2 == 0) num[nCnt++] = c - '0';
        else oper[oCnt++] = c;
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS에 대해 알아볼 수 있는 문제였습니다.