백준, BOJ, 16637번, 괄호추가하기 : C++ [CPP]

어려웠다.

사실 생각은 났는데 작성하기가 힘들다.

아직 구현하는 능력이 부족하다.

100문제밖에 안풀었는데 잘하길 바라는 것은 사치겠지

더군다나 시간제한이 있는 것으로 봐선.. 어려워보였지만

다행히 20개가 넘는 식은 안나와서 풀 수 있었다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <climits>


using namespace std;

int N;
string s;

int ans_M = INT_MIN;

//괄호를 씌웠을 때, 안씌웠을 때 모두 조사해본다.
//괄호에 의해서만 연산 순서가 정해진다 (모두 연산 순위 같음)


//연산
int operation(int a, int b, char c){
    int result;

    //c에 따라 결정
    switch(c){
        case '+': result = a+b; break;
        case '-': result = a-b; break;
        case '*': result = a*b; break;
    }
    return result;
}

void recursive(int idx, int untilnow){
    
    //끝까지 다계산했으면 종료
    if(idx > N-1){
        ans_M = max(ans_M, untilnow);
        return;
    }
    
    //만약 처음이 아니라면 이전 값과 어떤 연산을 해야하는지 알아야함
    char oper;
    if(idx != 0){
       oper = s[idx-1];
    }else{
        //처음이면 0과 더하면 됨.
        oper = '+';
    }
    
    
    //괄호로 묶을 수 있어야함. (idx,idx+1, idx+2를 이용)
    if(idx + 2 < N){
       //괄호로 묶어서 계산 -> 이전 값 (연산) 괄호 값(2개)
        
        int a,b;
        char c;
        a = s[idx]-'0';
        b = s[idx+2] -'0';
        c = s[idx+1];
        //이전값 : untilnow
        //지금값 : opertaion(a,b,c);
        int temp1 = operation(a,b,c);
        int sum1 = operation(untilnow, temp1, oper);
    
        //idx+3인것 같지만 3을 건너가면 연산자가나옴.
        recursive(idx+4, sum1); 
    }


    
    
    
    //안묶고 계산 -> 이전 값 (연산) 지금 값(1개)
    int temp2 = operation(untilnow, s[idx]-'0', oper);
    recursive(idx+2, temp2);
    
}


int main(){
    cin >> N >> s;
    
    //N개의 문자가 있음 N번째는 숫자 N-1번째는 연산자...
    recursive(0,0);
    
    cout << ans_M;
    
    
    return 0;
}

 

처음에 보자마자..

음 어떻게 해야하지?? 생각했고

연산자의 우선순위가 정해져있지 않기에

괄호 씌운 것과 안 씌운 것을 다 해보면 되겠다.라고 생각했다.

하지만 생각만큼 하기가 어려웠다.

 

1. 순서대로 연산하되

2. 괄호를 씌웠을 때 연산 어떻게?

2-1. 이전 값과 어떻게 합칠까?

2-2. 연산 후 그 다음엔?

3. 괄호를 씌우지 않았을 때 연산 어떻게?

3-1. 이전 값과 어떻게 합칠까?

3-2. 연산 후 그 다음엔?

4. 연산이 끝날 때를 어떻게 알지?

 

이런 생각이 들었던 것 같다.