프로그래머스 - 카드 게임

https://programmers.co.kr/learn/courses/30/lessons/42896

 

문제 설명

특별한 규칙의 카드 게임이 있다.
짝수 개의 카드를 무작위로 섞은 뒤, 같은 개수로 두 더미로 나눈다. 그리고 하나는 왼쪽, 하나는 오른쪽에 둔 뒤, 다음과 같은 규칙으로 진행한다.

1. 왼쪽 카드 또는 왼쪽 카드와 오른쪽 카드를 버릴 수 있다.
이 행동은 언제든지 가능하며, 점수를 획득하지는 않는다.  
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수 보다 작을 경우엔,
오른쪽 카드만 버릴 수 있다. 이 때, 오른쪽 카드에 적힌 수 만큼 점수를 얻는다.  
3. 왼쪽 또는 오른쪽 카드를 모두 버릴 때 까지 진행한다.

왼쪽과 오른쪽 카드의 정보를 토대로, 얻을 수 있는 최종 점수의 최댓값을 리턴하자.

 

제한 사항

• 1 <= 한 더미의 카드 수 <= 2,000
• 1 <= 카드에 적힌 수 <= 2,000
• 같은 숫자의 카드가 있을 수 있다.
• 왼쪽 카드의 수는 오른쪽 카드의 수와 같다.

 

1. DP - O(N^2)

얼핏 봐서는 쉬워보이는 문제일 수 있으나, 생각보다 까다롭다.

“왼쪽 카드의 제일 큰 수보다 작은 오른쪽 카드 수를 다 더하면 되지 않아?” 라고 하기에는 오른쪽 카드에 그 수 보다 더 큰수들이 나타나면 오답을 내기 마련이다.

[3,5,2,1], [6,1,6,4]

위의 경우에서는 5보다 작은 1과 4가 있지만, 왼쪽에 5를 둔 채로는 맨 뒤의 4를 만날 수 없기 때문이다. 오른쪽 카드만 버릴 수 있는 경우는 왼쪽 카드의 숫자가 오른쪽 카드의 숫자보다 클 때뿐이다.

그러면 어떻게 해야 할까?

 

지금까지 i장의 왼쪽 카드와 j장의 오른쪽 카드를 버렸다고 생각해보자. 그리고 지금까지 얻은 점수를 s라고 하자.

그러면 i+1장의 왼쪽 카드와 j장의 오른쪽 카드를 버렸을 경우,
최소한 s의 점수를 보장받을 수 있다. 왜냐하면 현재 상태에서 왼쪽 카드만 한 장 버린다면, 점수는 그대로 s로 유지되기 때문이다.

만약 다른 방법을 써서 s보다 더 큰 점수를 얻고 있었다면, 점수 s는 무시해도 된다. 똑같이 i+1, j장을 버렸을 때 최댓값이 중요하기 때문이다.

따라서, d[i][j]를 i장의 왼쪽 카드와 j장의 오른쪽 카드를 버렸을 때의 최고 점수라고 했을 때, 다음과 같이 표현할 수 있을 것이다.
(0 <= i,j, <= 카드 갯수 )

d[i+1][j] = max(d[i+1][j], d[i][j])

그리고 왼쪽 카드와 오른쪽 카드를 동시에 버리는 경우도 점수는 그대로 유지된다. 따라서 다음과 같은 표현도 가능할 것이다.

d[i+1][j+1] = max(d[i+1][j+1], d[i][j])

만약, 지금의 왼쪽 카드가 지금의 오른쪽 카드보다 숫자가 크다면, 오른쪽 카드만 버리는 행동이 가능해진다. 따라서 다음과 같은 표현이 조건부로 가능해진다.

d[i][j+1] = max(d[i][j+1], d[i][j] + right[j]) (if left[i] > right[j])

그렇다면, 가능한 모든 d[i][j]에 대해 위의 수식을 실행시킨다면, i == 카드 수 또는 j == 카드 수가 되는 d[i][j]중 최댓값을 찾으면 이 문제의 해답이 될 것이다.

 

여기서 주의해야 할 점이 하나 있다.
d[i][j]라고 해도, 실제로 i와 j가 도달할 수 있는 지점인지 확인을 해야 한다. 이것이 무슨말인지 궁금해 할 수 있는데, 위의 예시를 다시 한번 살펴보자.

[3,5,2,1], [6,1,6,4]

여기서 i=0, j=3이 가능한 일일까?
위의 경우의 수가 가능해지려면, 맨 첫번째 왼쪽 카드는 맨 처음으로 나오는 오른쪽의 카드 3장과 비교해서 더 커야한다. 왜냐하면 오른쪽 카드만 버릴 수 있는 경우는 왼쪽 카드가 오른쪽 카드보다 큰 경우밖에 없기 때문이다.
따라서, 이에 대한 고려를 하지 않는 경우에는 오답이 나올 수 있다.

그러면 이를 어떻게 대처할까?

맨 처음에 d 배열을 만들 때, 모든 값을 -1등의 음수로 초기화하자.
맨 처음으로 시작하는 경우인 d[0][0]의 값만 0으로 초기화 하자. 그리고 위의 수식을 d[i][j] >= 0일 때만 수행하도록 하는 것이다. 그러면 d[0][3]의 값은 계속 -1로 유지되어 도달할 수 없는 경우의 수로 간주하여 넘어가게 될 것이다.

 

그러면 위의 내용을 코드로 표현해보자.

 

solution.cpp

#include <vector>

using namespace std;

int solution(vector<int> left, vector<int> right) {
	int l = left.size();
	vector<vector<int>> d(l + 1, vector<int>(l + 1, -1));
	d[0][0] = 0;

	for (int i = 0; i < l; ++i)
	{
		for (int j = 0; j < l; ++j)
		{
			if (0 <= d[i][j])
			{
				d[i + 1][j] = max(d[i + 1][j], d[i][j]);
				d[i + 1][j + 1] = max(d[i + 1][j + 1], d[i][j]);

				if (left[i] > right[j])
					d[i][j + 1] = max(d[i][j + 1], d[i][j] + right[j]);
			}
		}
	}

	int answer = 0;
	for (int i = 0; i < l; ++i)
		answer = max(answer, max(d[i][l], d[l][i]));
	return answer;
}

 

동적 계산법 문제의 경우, 점화식을 잘 세워야 하는 문제들이 종종 나온다. 여러 문제들을 풀면서 점화식을 어떻게 세워야 할 지에 대해 고민을 많이 해보자.