[C++] 백준 11062. 카드 게임

https://www.acmicpc.net/problem/11062

11062번: 카드 게임

 

 

아이디어

처음에는 그리디 알고리즘 문제인줄 알고

deque를 이용해서 현재 최고 가치를 가지는 카드를 뽑는 방식을 로직을 사용했는데,

최선의 전략으로 게임이 끝났을 때, 최고 점수를 얻어야 하는 것이더라구요.

 

그러면 현재 최선의 선택잉 미래에는 최선이 아닐 수 있습니다.

이럴 때는 다이나믹 프로그래밍을 사용해야죠!

 

 dp[i][j] 는

i번째 카드 ~ j번째 카드가 있을 때, 근우의 최대 점수를 뜻합니다.

 

dp[i][j] 는

왼쪽카드 + dp[i+1][j]

오른쪽카드 + dp[i][j-1]

 

둘 중에 최대값을 골라서 갱신할 수 있죠.

한 번 로직을 짜보겠습니다.

 

풀이

 

필요한 변수를 초기화 하는 부분입니다.

 

 

메인 함수쪽에서 입력을 받는 부분입니다.

테스트 케이스를 입력해줘야해서 추가적인 입력 로직을 만들어주었고,

메인 루프가 존재합니다.

 

루프쪽 입력에서는 

카드의 개수, dp 초기화, 카드의 정보를 받아주고 있습니다.

 

 

이건 로직부분인데,

Top-Down 방식이 아닌 Bottom-Up 방식의 DP를 사용했습니다.

 

 

left > right 인 경우에는 Logic이 끝나도록 설정했고

dp가 이미 계산된 경우에는 굳이 계산하지 않습니다. 

 

turn % 2 == 0 인 경우는 근우의 차례입니다.

근우는 왼쪽 카드를 고르거나, 오른쪽 카드를 고를 수 있고 둘 중에 최대값을 점수로 가집니다.

 

turn % 2 == 1 인 경우는 명우의 차례입니다.

명우도 왼쪽 카드를 고르거나, 오른쪽 카드를 고를 수 있습니다.

dp자체가 근우의 점수를 뜻하는 것이므로,

cards를 더해주지 않습니다.

 

그리고 명우가 min 함수를 쓰는 이유는,

로직 자체가 근우가 최대 점수를 얻도록 유도하고 있기 때문에

최소 로직을 골라야 명우 입장에선 최선의 경우가 되는 것입니다.

 

아래는 전체코드 입니다.

 

#include <iostream>
#include <vector>
using namespace std;

int testCase;
int cardCnt;
int cards[1001];
vector<vector<int>> dp;

int Logic(int left, int right, int turn)
{
	if (left > right) return 0;
	
	if (dp[left][right]) return dp[left][right];

	if (turn % 2 == 0)
		return dp[left][right] = 
		max(cards[left] + Logic(left + 1, right, turn + 1), cards[right] + Logic(left, right - 1, turn + 1));
	else
		return dp[left][right] =
		min(Logic(left + 1, right, turn + 1), Logic(left, right - 1, turn + 1));
}

int main()
{
	/* 입력1 */
	{
		cin >> testCase;
	}

	/* 루프 */
	for (int test = 0; test < testCase; test++)
	{

		/* 입력 */
		{
			cin >> cardCnt;

			dp = vector<vector<int>>(cardCnt, vector<int>(cardCnt, 0));


			for (int i = 0; i < cardCnt; i++)
				cin >> cards[i];
			
		}

		/* 로직 */
		{
			Logic(0, cardCnt - 1, 0);
		}

		/* 출력 */
		{
			cout << dp[0][cardCnt - 1] << endl;
		}

	}
}