문제 설명
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.
근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.
예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.
https://www.acmicpc.net/problem/11062
제한 사항
풀이
문제를 요약하면, 카드의 양끝을 선택하는 게임을 하는데 첫 번째 플레이어가 얻을 수 있는 최대 점수를 구하는 것이다.
해당 문제의 핵심은 다음과 같다.
두 플레이어는 번갈아가면서 최선의 선택을 한다.
또한, 정해진 총합에서 두 플레이어는 점수를 나눠갖는다.
첫 번째 플레이어가 최대 점수를 얻기 위해서는 두 번째 플레이어가 최소 값을 얻게 해야 한다.
이 말을 다르게 표현하면 두 번째 플레이어의 점수는 첫 번째 플레이어 잃는 점수와 같다.
예를 들어 보자.
1, 3, 15, 1, 19, 2카드가 위와 같을 때, 첫 번째 플레이어는 1과 2중 선택을 해야 한다.
만약, 2가 1보다 크기 때문에 탐욕법을 적용해서 2를 선택한다면 두 번째 플레이어는 1과 19중 고르게 된다.
두 번째 플레이어 역시 최선의 선택을 하기 때문에 19를 고를 것이다.
그러면 첫 번째 플레이어는 19점을 잃은 것과 같다.
즉, 첫 번째 플레이어는 카드를 선택할 때 자신이 가질 수 있는 최대 점수와 상대가 가질 수 있는 최소 점수를 계산하여 최선의 선택을 해야 한다.
이를 MiniMax 알고리즘이라고 한다.
코드를 간단하게 적어보면 다음과 같다.
int TakeCard(int left, int right, bool bMax)
{
if (left > right) return 0;
if (bMax)
{
return max(cards[left] + TakeCard(left + 1, right, false), cards[right] + TakeCard(left, right - 1, false));
}
else
{
return min(TakeCard(left + 1, right, true), TakeCard(left, right - 1, true));
}
}bMax는 최대 점수를 만들지 최소 점수를 만들지 결정하는 변수이다.
즉, bMax가 true라면 첫 번째 플레이어의 입장이고 false라면 두 번째 플레이어의 입장이 된다.
첫 번째 플레이어의 입장을 생각해 보면 왼쪽에 고를 때와 오른쪽에서 고를 때 점수를 얻게 된다.
이 값을 최대로 만들어야 한다.
두 번째 플레이어의 입장을 생각해보면 마찬가지로 왼쪽과 오른쪽에서 카드를 고른다.
두 번째 플레이어 역시 최대 점수를 만들 것이고 이는 첫 번째 플레이어가 잃는 점수와 같기에 min값을 취한다.
하지만, 우리가 알고 싶은 값은 첫 번째 플레이어의 점수이기 때문에 점수를 더하지는 않는다.
즉, 최대-최소-최대-최소를 번갈아가며 선택했을 경우를 살펴보는 것이다.
하지만 해당 문제는 이렇게만 구현한다면 시간초과가 발생한다.
이를 해결하기 위해 left, right를 기준으로 점수를 기록하면 시간을 줄일 수 있다.
즉, dp를 이용하는 것이다.
int TakeCard(int left, int right, bool bMax)
{
if (left > right) return 0;
if (dp[left][right] != 0) return dp[left][right];
if (bMax)
{
return dp[left][right] = max(cards[left] + TakeCard(left + 1, right, false), cards[right] + TakeCard(left, right - 1, false));
}
else
{
return dp[left][right] = min(TakeCard(left + 1, right, true), TakeCard(left, right - 1, true));
}
}
전체 코드
#include <bits/stdc++.h>
using namespace std;
int T, N;
vector<int> cards;
int dp[1001][1001];
int TakeCard(int left, int right, bool bMax)
{
if (left > right) return 0;
if (dp[left][right] != 0) return dp[left][right];
if (bMax)
{
return dp[left][right] = max(cards[left] + TakeCard(left + 1, right, false), cards[right] + TakeCard(left, right - 1, false));
}
else
{
return dp[left][right] = min(TakeCard(left + 1, right, true), TakeCard(left, right - 1, true));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> T;
while (T--)
{
cin >> N;
cards.resize(N);
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++)
{
cin >> cards[i];
}
cout << TakeCard(0, N-1, true) << "\n";
}
return 0;
}