알고리즘/기타

백준 6064 - 카잉 달력

hvv_an 2025. 6. 12. 10:49

문제 설명

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다. 

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

  1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
  2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
  3. (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;
}