[백준] 16637번: 괄호 추가하기 (C++)

16637번: 괄호 추가하기

---

문제)

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

 

 

 

입력 :

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

 

 

출력 :

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

 

 

 

풀이)

 

괄호를 추가했을 때와, 추가하지 않았을 때의 상태를 가정하여 dfs를 진행했다.

괄호를 추가했다고 가정했을 때는 현재 위치에 +4를 하여 -1, -3 상태의 숫자를 먼저 temp에 구해 이전 결과에 연산해주었고,

추가하지 않았다고 가정했을 경우에는 차근차근 연산자를 이용하여 연산해주었다.

 

이 문제에서 가장 어려웠던 점은.

cnt가 n에 도달했을 때, 마지막 연산을 빼먹는 경우가 있었을 경우였다.

이는 내가 cnt, 즉 현재 보고 있는 문자를 제대로 체크하지 못해서였다.

 

소스코드는 다음과 같다.

 

#include <iostream>
#include <string>
#include <limits.h>
 
using namespace std;
 
int n;
// 식의 최댓값을 구해야 함.
int ans = INT_MIN;
 
string modi;
 
void dfs(int result, int cnt, bool flag)
{
    if (cnt > n)
    {
        ans = max(result, ans);
        return;
    }
 
    // 괄호를 안 친 경우
    if (flag == 0)
    {
        if (modi[cnt - 1] == '+')
        {
            result = result + (modi[cnt] - '0');
            dfs(result, cnt + 2, 0);
            if (cnt + 4 <= n)
            {
                dfs(result, cnt + 4, 1);
            }
        }
        else if (modi[cnt - 1] == '-')
        {
            result = result - (modi[cnt] - '0');
            dfs(result, cnt + 2, 0);
            if (cnt + 4 <= n)
            {
                dfs(result, cnt + 4, 1);
            }
        }
        else if (modi[cnt - 1] == '*')
        {
            result = result * (modi[cnt] - '0');
            dfs(result, cnt + 2, 0);
            if (cnt + 4 <= n)
            {
                dfs(result, cnt + 4, 1);
            }
        }
    }
    else // 괄호를 친 경우, 닫아야 함.
    {
        int temp;
        if (modi[cnt - 1] == '+')
        {
            temp = (modi[cnt - 2] - '0') + (modi[cnt] - '0');
        }
        else if (modi[cnt - 1] == '-')
        {
            temp = (modi[cnt - 2] - '0') - (modi[cnt] - '0');
        }
        else if (modi[cnt - 1] == '*')
        {
            temp = (modi[cnt - 2] - '0') * (modi[cnt] - '0');
        }
 
 
        if (modi[cnt - 3] == '+')
        {
            result = result + temp;
        }
        else if (modi[cnt - 3] == '-')
        {
            result = result - temp;
        }
        else if (modi[cnt - 3] == '*')
        {
            result = result * temp;
        }
 
        dfs(result, cnt + 2, 0);
        if (cnt + 4 <= n)
        {
            dfs(result, cnt + 4, 1);
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    cin >> modi;
 
    if (n >= 4)
    {    // n이 4 이상일 경우, 괄호의 여부가 나뉘어진다.
        dfs(stoi(modi.substr(0, 1)), 2, false);
        dfs(stoi(modi.substr(0, 1)), 4, true);
    }
    else if (n == 3)
    {    // n == 3일 경우 괄호가 의미가 없음
        dfs(stoi(modi.substr(0, 1)), 2, false);
    }
    else
    {
        cout << modi;
        return 0;
    }
 
    cout << ans;
    return 0;
}

+ 좀 더 쉬운 풀이

이 풀이에서는 oper에 따른 연산을 모듈화하고, 더 읽기 쉽고 이해하기 편하도록 재귀함수를 이용하여 소스코드가 짜여져 있다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
vector<int> nums;
vector<char> opers;
 
int n;
string temp;
int ans = INT_MIN;
 
int operating(char a, int b, int c)
{
    if (a == '+') return b + c;
    if (a == '-') return b - c;
    if (a == '*') return b * c;
}
 
void go(int here, int result)
{
    if (here == nums.size() - 1)
    {
        ans = max(ans, result);
        return;
    }
 
    go(here + 1, operating(opers[here], result, nums[here + 1]));
 
    if (here + 2 <= nums.size() - 1)
    {
        int temp = operating(opers[here + 1], nums[here + 1], nums[here + 2]);
        go(here + 2, operating(opers[here], result, temp));
    }
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    cin >> temp;
 
    for (int i = 0; i < temp.length(); i++)
    {
        if (i % 2 == 0) nums.push_back(temp[i] - '0');
        else opers.push_back(temp[i]);
    }
 
    go(0, nums[0]);
 
    cout << ans;
    
 
 
    return 0;
}

 

 

 

---

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

16637번: 괄호 추가하기