괄호 추가하기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
/* 정답범위가 -2^31보다 크며 2^31보다 작으니까 매우 작은 음수로 설정해야 한다 */
int N,ans=INT_MIN; // int범위 최소값으로 지정
string s;
int calc(int a, int b, char c)
{
    switch (c)
    {
        case '+': return a+b;
        case '-': return a-b; 
        case '*': return a*b; 
        default : return 0; 
    }
}
void DFS(int idx, int tot){
    /* base condition */
    if(idx >= s.length()){
        ans = max(ans, tot);
        return;
    }
    /* 현재 연산자 괄호 O */
    int val1 = calc(tot, s[idx+1]-'0', s[idx]);
    DFS(idx+2, val1);
    /* 다음 연산자 괄호 O */
    if(idx+3 < s.length()){
        int val2 = calc(s[idx+1]-'0', s[idx+3]-'0', s[idx+2]);
        int val3 = calc(tot, val2, s[idx]);
        DFS(idx+4, val3);
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> s;
    DFS(1, s[0]-'0');
    cout << ans;
    return 0;
}

• 문제 풀이
  • 최초 시도
    : 모든 연산자 개수 중 우선순위 조합을 만들어서 실행하려 했으나 실행 코드를 짜지 못해 실패
    (괄호가 겹치는 경우의 우선순위를 찾는것도 확실하지 않았음)
  • 결과
    : 정답 풀이를 참조

• (핵심) 현재 연산자를 기준으로 2가지 경우를 수행
  • 현재 연산자를 기준으로 괄호를 묶었을 경우
    --> 현재 연산자를 기준으로 앞 / 뒤에있는 숫자에 대해 수행 후 DFS()
  • 다음 연산자를 기준으로 괄호를 묶고, 해당 결과를 누적값과 현재 연산자로 계산
    --> 다음 연산자를 기준으로 계산한 뒤, 현재 연산자를 처리하고 DFS() 수행
    ex) 3+8*7-9*2 에서
    +가 현재 연산자 일 때,
    다음 연산자인 *을 괄호로 묶었다고 가정하고 미리 연산을 수행하면8*7=56이고,
    현재 연산자와 누적값(3)을 계산하면 3+56=59가 된다

• 주의
  : max값을 저장하는 ans변수의 초기값이 INT_MIN값을 가져야 함
  (정답의 범위가 최소 -2^31+1 이기 때문)