문제 설명
지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.
이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.
- 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
- 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
- (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.
다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다
카드 순서왼쪽 더미오른쪽 더미
| 1 | 3 | 2 |
| 2 | 2 | 4 |
| 3 | 5 | 1 |
이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.
두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.
https://www.acmicpc.net/problem/10835
제한 사항
풀이
문제를 요약하면 두 개의 카드더미가 주어지고 이를 적절히 선택하여 최대 점수를 얻는 것이다.
선택 규칙은 다음과 같다.
- 왼쪽 카드만 버린다 → 점수 없음
- 오른쪽 카드가 더 작을 때 오른쪽 카드만 버린다 → 오른쪽 카드 숫자만큼 점수 획득
- 둘 다 버린다 → 점수 없음
문제를 읽으면 완전 탐색으로 풀 수 있다고 생각이 들 것이다.
오른쪽 카드가 작을때는 무조건 버리고 그렇지 않으면 왼쪽만 버리거나 둘 다 버리는 방식으로 전개할 수 있다.
하지만 이렇게 모두 탐색하게 된다면 시간 초과가 발생한다.
따라서 메모이제이션을 통해 가지 치기를 진행해야 한다.
분기를 잘라내는 규칙은 간단하다.
왼쪽, 오른쪽 더미의 가장 윗 카드의 조합마다 최대 점수를 기록해 놓으면 된다.
예를 들어 보자.
3
3 2 5
2 4 1이러한 입력이 있을 때 처음은 왼쪽 카드가 3, 오른쪽 카드가 2이다.
어떠한 상황이든 선택할 수 있는 경우는 왼쪽만 버리거나 둘 다 버리는 경우이다.
dp[l][r] = max(DFS(l + 1, r), DFS(l + 1, r + 1));그리고 현재는 오른쪽 카드가 더 작기 때문에 오른쪽 카드만 버려 점수를 얻을 수도 있다.
if (leftCards[l] > rightCards[r])
{
dp[l][r] = max(dp[l][r], DFS(l, r + 1) + rightCards[r]);
}
이렇게 기록된 dp의 값이 -1(초기값)이 아니라면 해당 분기는 처리된 분기이기 때문에 더 이상 진행하지 않아도 된다.
if (dp[l][r] != -1) return dp[l][r];
이렇게 모든 분기를 처리하면 왼쪽 혹은 오른쪽 카드 더미가 모두 비워지는 경우가 생길 것이고 그때 최댓값을 반환하면 정답을 구할 수 있다.
int DFS(int l, int r)
{
// 가지치기
if (l == N || r == N) return 0;
if (dp[l][r] != -1) return dp[l][r];
dp[l][r] = max(DFS(l + 1, r), DFS(l + 1, r + 1));
//오른쪽 버리기
if (leftCards[l] > rightCards[r])
{
dp[l][r] = max(dp[l][r], DFS(l, r + 1) + rightCards[r]);
}
return dp[l][r];
}
전체 코드
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
using namespace std;
int N;
vector<int> leftCards;
vector<int> rightCards;
vector<vector<int>> dp;
int ans = 0;
int DFS(int l, int r)
{
// 가지치기
if (l == N || r == N) return 0;
if (dp[l][r] != -1) return dp[l][r];
dp[l][r] = max(DFS(l + 1, r), DFS(l + 1, r + 1));
//오른쪽 버리기
if (leftCards[l] > rightCards[r])
{
dp[l][r] = max(dp[l][r], DFS(l, r + 1) + rightCards[r]);
}
return dp[l][r];
}
int main()
{
INPUT_OPTIMIZE;
cin >> N;
leftCards.resize(N);
rightCards.resize(N);
dp.resize(N, vector<int>(N, -1));
for (int i = 0; i < N; i++)
{
cin >> leftCards[i];
}
for (int i = 0; i < N; i++)
{
cin >> rightCards[i];
}
cout << DFS(0, 0);
return 0;
}