사칙연산 programmers
- (((1 - 3) + 5) - 8) = -5
- ((1 - (3 + 5)) - 8) = -15
- (1 - ((3 + 5) - 8)) = 1
- (1 - (3 + (5 - 8))) = 1
- ((1 - 3) + (5 - 8)) = -5
사칙연산에서 -는 결합법칙이 성립되지 않는다.
위와같이 -의 연산순서에 의해 값이 달라질 수 있다.
수와 연산자가 주어질때 최대값을 구하는 문제다.
1, 2번을 풀고 남은 2시간50분동안 시도했지만 못풀었다.
첫 번째로 string입력으로 들어오는데 단순하게 생각해서 숫자 string의 값을 0번 인덱스만 받아서
이 오류를 찾는데 1시간이 지나고서야 알게되었다.
두 번째로 dp를 떠올려서 dp로 맞는 방법으로 접근하긴 했지만 너무 단순하게 생각했다.
풀이는 해설에서 아주 잘 설명하고있으니 그것으로 대체한다.
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define INF 987654321
int dp[202][202][2];
int N;
vector<int> num;
int solve(int l, int r, int flag) {
int &ret = dp[l][r][flag];
if (ret != -1) return ret;
ret = 0;
if (flag) { //최솟값
for (int next = l;next <= r;next++) {
if (next == l && num[next] < 0) ret += (-num[next]);
else ret += num[next];
}
for (int next = l;next < r;next++) {
if (num[next + 1] < 0) {
ret = min(ret, solve(l, next, 1) - solve(next + 1, r, 0));
}
else {
ret = min(ret, solve(l, next, 1) + solve(next + 1, r, 1));
}
}
}
else { //최댓값
for (int next = l;next <= r;next++) {
if (next == l && num[next] < 0) ret += (-num[next]);
else ret += num[next];
}
for (int next = l;next < r;next++) {
if (num[next + 1] < 0) {
ret = max(ret, solve(l, next, 0) - solve(next + 1, r, 1));
}
else {
ret = max(ret, solve(l, next, 0) + solve(next + 1, r, 0));
}
}
}
return ret;
}
int solution(vector<string> in) {
num.clear();
memset(dp, -1, sizeof dp);
int data = 0;
for (int m = in[0].size() - 1, t = 1;m >= 0;m--, t *= 10) data += (in[0][m] - '0')*t;
num.push_back(data);
for (int n = 1;n < in.size();n++) {
if (!(n & 1)) {
data = 0;
for (int m = in[n].size() - 1, t = 1;m >= 0;m--, t *= 10) data += (in[n][m] - '0')*t;
num.push_back((in[n - 1][0] == '-' ? -data : data));
}
}
N = num.size();
int ans = solve(0, N - 1, 0);
return ans;
}
| cs |
댓글 없음:
댓글 쓰기