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

예전에 풀어본적이 있던 유형의 문제 같은데 풀이가 잘 생각나지 않았다.

다른 사람의 풀이를 보고 대충 힌트를 얻어 구현했다.

 

<문제>

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

16637번: 괄호 추가하기

 

 

<참고해서 푼 풀이>

#include<bits/stdc++.h>
using namespace std;

int n, result = INT_MIN;
string s;

int cal(int a, int b, char op){
  switch(op){
    case '+': a += b; break;
  	case '*': a *= b; break;
  	case '-': a -= b; break;
  }
  return a;
}

void dfs(int index, int num){
  if(index > n-1){
    result = max(result, num);
    return;
  }
  
  char op = (index == 0)? '+' : s[index-1];
  
  //괄호로 묶기
  if(index + 2 < n){
    int br = cal(s[index] - '0', s[index+2] - '0', s[index+1]);
    dfs(index+4, cal(num, br, op));
  }
  //괄호로 안묶기
  dfs(index+2, cal(num, s[index]-'0', op));
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  cin>>n>>s;
  dfs(0,0);
  cout<<result;
}

dfs를 이용하여 푸는 문제였다.

괄호로 묶거나 안묶거나하여 계산한 모든 경우의수를 계산하여 가장 큰 값을 구하도록 했다.

이전의 계산 값인 num에 이번 계산값과 연산하는 방식이다.