Compy's Blog
206 words
1 minutes
[BOJ] 괄호 추가하기
2025-04-02

괄호 추가하기

TimeLimitMemoryLimitConditionTAG
0.5s512MB(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/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-04-02