ps
[백준] 11062 - 카드 게임
kariskan
2022. 8. 22. 21:58
https://www.acmicpc.net/problem/11062
11062번: 카드 게임
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는
www.acmicpc.net
약간 까다로운 dp 문제였다. dp 배열의 정의는 제대로 했는데, dp를 적용시키는 과정에서 약간 어려웠다.
dp[i][j] = i번째 카드부터 j번째 카드까지 남아있을 때, 얻을 수 있는 최대 점수
로 정의해서, dp[1][n]을 top-down 방식으로 구하면 된다.
게임 이론 문제 같은 경우에는 양 측이 항상 최선의 방식대로 진행한다.
그래서 양 측 턴이 번갈아 가면서 최선의 선택을 했을 때 최댓값을 구해야한다.
그래서, 자신의 턴인 경우에 max(좌측 점수 + dp[l + 1][r], 우측 점수 + dp[l][r - 1]) 이고,
상대의 턴인 경우에는 나의 점수를 최소화해야 하기 때문에 min(dp[l + 1][r], dp[l][r - 1]) 이다.
#include <iostream>
#include <cstring>
using namespace std;
int n, a[1010], dp[1010][1010];
int go(int l, int r) {
if (l > r)return 0;
if (dp[l][r])return dp[l][r];
if ((n - r + l) % 2 != 0) { //1턴
return dp[l][r] = max(a[l] + go(l + 1, r), a[r] + go(l, r - 1));
}
else { //2턴
return dp[l][r] = min(go(l + 1, r), go(l, r - 1));
}
}
int main() {
int t; cin >> t;
while (t--) {
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << go(1, n) << '\n';
}
return 0;
}