[백준 16637]괄호 추가하기
A. 접근법
연산자 우선순위가 동일하기 때문에 왼쪽부터 계산한다는 조건, 괄호 안에는 연산자가 하나만 있어야 한다는 조건으로 인해서 문제 접근은 DP로 접근해야겠다는 생각이 들었다.(시간 제한도 0.5초로 짧다)
dp[N]: N개의 숫자가 주어졌을 때 괄호를 추가해서 얻을 수 있는 최대값을 저장하는 배열.
mdp[N]: N개의 숫자가 주어졌을 때 괄호를 추가해서 얻을 수 있는 최소값을 저장하는 배열.
dp[N]는 아래 셋 중에 최대값을 저장해야한다.
- dp[N - 1]과 N번째 숫자를 계산
- dp[N - 2]와 (N, N - 1번째 숫자를 계산한 값)을 계산.
- mdp[N - 2]와 (N, N - 1번째 숫자를 계산한 값)을 계산. -> mdp[N - 2]가 음수인데 (N, N - 1)을 계산한 것이 음수여서 둘이 곱하여서 최대값이 될 수있다.
처음에는 3번 조건을 고려하지 않아 틀려서 문제의 질문 검색을 통해서 알게되었다.
B. 구현
C. 코드
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
#define ll long long
char fm[19];
// 최대값을 저장하는 배열.
vector<ll> dp;
// 최소값을 저장하는 배열.
vector<ll> mdp;
int T, N;
// 문자로 된 값과 연산자를 통해 계산하는 함수.
ll cal(ll a, ll b, char c) {
ll ret = 0;
switch(c) {
case '+':
ret = a + b;
break;
case '-':
ret = a - b;
break;
case '*':
ret = a * b;
break;
default:
//cout << "NO!" << endl;
break;
}
return ret;
}
void solver(int n) {
if(n == 0) {
dp.push_back(atoi(&fm[0]));
mdp.push_back(atoi(&fm[0]));
}
else if(n == 1) {
dp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
mdp.push_back(cal(atoi(&fm[0]), atoi(&fm[2]), fm[1]));
}
else {
ll a = dp[dp.size() - 2];
ll b = dp[dp.size() - 1];
ll c = mdp[mdp.size() - 2];
ll d = mdp[mdp.size() - 1];
char oa = 2 * (n - 2) + 1;
char ob = 2 * (n - 1) + 1;
dp.push_back(max(cal(b, atoi(&fm[2 * n]), fm[ob]), cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
dp[dp.size() - 1] = max(dp[dp.size() - 1], cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));
mdp.push_back(min(cal(d, atoi(&fm[2 * n]), fm[ob]), cal(c, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa])));
mdp[dp.size() - 1] = min(mdp[mdp.size() - 1], cal(a, cal(atoi(&fm[2 * (n - 1)]), atoi(&fm[2 * n]), fm[ob]), fm[oa]));
}
if(N / 2 == n)
return;
else
solver(n + 1);
}
int main() {
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
scanf("%d", &N);
scanf("%s\n", fm);
dp.clear();
mdp.clear();
solver(0);
printf("%d\n", dp[dp.size() - 1]);
}
return 0;
}
D. 결과
Author And Source
이 문제에 관하여([백준 16637]괄호 추가하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pamrk2002/백준-16637저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)