알고스팟 NUMBERGAME https://algospot.com/judge/problem/read/NUMBERGAME
두 사람이 최적의 판단을 했을 때 결과를 구하는 문제이다.
게임이론(mini-max algorithm) 과 dp로 해결할 수 있다.
첫번째 문제는 첫주자의 얻을 수 있는 최댓값을 구하는 문제이다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N;
int score[1111];
int dp[1111][1111][2];
int solve(int l, int r, int flag) {
if (l > r) return 0;
int &ret = dp[l][r][flag];
if (ret != -INF) return ret;
if (!flag) {
ret = -INF/2;
ret = max(ret, solve(l + 1, r, 1) + score[l]);
ret = max(ret, solve(l, r - 1, 1) + score[r]);
}
else {
ret = INF/2;
ret = min(ret, solve(l + 1, r, 0));
ret = min(ret, solve(l, r - 1, 0));
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
for (int n = 0;n < 1111;n++)for (int m = 0;m < 1111;m++) dp[n][m][0] = dp[n][m][1] = -INF;
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &score[n]);
printf("%d\n", solve(0, N - 1, 0));
}
return 0;
}
| cs |
두 번째 문제는 두 사람의 점수 차이를 구하는 문제이다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N;
int score[51];
int dp[51][51][2];
int solve(int l, int r, int flag) {
if (l > r) return 0;
int &ret = dp[l][r][flag];
if (ret != -INF) return ret;
if (!flag) {
ret = -INF/2;
if (r - l + 1 >= 2) {
ret = max(ret, solve(l + 2, r, 1));
ret = max(ret, solve(l, r - 2, 1));
}
ret = max(ret, solve(l + 1, r, 1) + score[l]);
ret = max(ret, solve(l, r - 1, 1) + score[r]);
}
else {
ret = INF/2;
if (r - l + 1 >= 2) {
ret = min(ret, solve(l + 2, r, 0));
ret = min(ret, solve(l, r - 2, 0));
}
ret = min(ret, solve(l + 1, r, 0) - score[l]);
ret = min(ret, solve(l, r - 1, 0) - score[r]);
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
for (int n = 0;n < 51;n++)for (int m = 0;m < 51;m++) dp[n][m][0] = dp[n][m][1] = -INF;
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &score[n]);
printf("%d\n", solve(0, N - 1, 0));
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기