206 words
1 minutes
[BOJ] 괄호 추가하기
| TimeLimit | MemoryLimit | Condition | TAG | 
|---|---|---|---|
| 0.5s | 512MB | (1 ≤ N ≤ 19) | BruteForce | 
각 괄호를 어떻게 칠까? 이거를 그냥 N의 범위가 엄청 작기 때문에 무조건 시간 안에 돌아갈 수 있다고 판단! 그래서 그거 토대로 구현하면 됩니다.
정답 코드
#include <iostream>
#define inf 1000000000
using namespace std;
using ll = long long;
int nums[20];
char operators[20];
int n;
void calc(int current, ll* value, ll calc_value){
    switch(operators[current-1]){
        case '*':
            *value *= calc_value;
            break;
        case '+':
            *value += calc_value;
            break;
        case '-':
            *value -= calc_value;
            break;
    }
}
ll solution(int current, ll current_result){
    if(current >= n) return current_result;
    ll result = -inf;
    
    ll nonWrap = current_result;
    calc(current, &nonWrap, nums[current]);
    
    
    if(current < n-1){
        ll wrap = nums[current];
        calc(current+1, &wrap, nums[current+1]);
        
        
        ll wrap_result = current_result;
        calc(current, &wrap_result, wrap);
        
        
        result = max(result, solution(current+2, wrap_result));
    }
    result = max(result, solution(current+1, nonWrap));
    
    return result;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        if(i%2 == 0) cin >> nums[i/2];
        else cin >> operators[i/2];
    }
    
    
    cout << solution(1, nums[0]);   
    
    
    return 0;
}[BOJ] 괄호 추가하기
https://compy07.github.io/Blog/posts/boj/16637/
