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/