백준 11062 카드게임

알고리즘/문제풀이

백준 11062 카드게임

마빈스펙트럼 2021. 6. 3. 20:17

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

11062번: 카드 게임

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는

www.acmicpc.net

풀이

DP배열을 정의합니다.

t가 0이면 근우, 1이면 명우 라고 정의하겠습니다.

DP[l][r][t] //l번에서 r번까지의 카드가 남은 상태이고 t라는 사람의 턴에 근우가 가진 점수

예제를 통해서 이야기하겠습니다.

4
1 2 5 2

처음 상태입니다. 근우는 두가지 선택지가 있습니다.

가장 왼쪽 카드를 가져오는 선택지, 가장 오른쪽 카드를 가져오는 선택지

근우가 선택을 했을때 나오는 경우의 수는 위의 그림과 같습니다.

여기서 근우는 자신의 점수가 커지는 선택을 해야한다는 사실을 염두해야합니다.

이것을 통해 점화식을 생각해보면 다음과 같습니다.

DP : l에서 r까지 카드가 남았고 t라는 사람의 차례일때 근우가 가지고 있는 점수
Arr : i번째 카드의 점수
t : 0이면 근우,1이면 명우
nt : t라는 사람의 다음사람

if(t == 0)
DP[l][r][t] = max(DP[l + 1][r][nt] + Arr[l], DP[l][r - 1][nt] + Arr[r]);

이제 명우의 차례입니다.

명우도 마찬가지로 두가지 선택지가 존재합니다.

가장 왼쪽 카드를 가져오는 선택지, 가장 오른쪽 카드를 가져오는 선택지

명우가 선택을 했을때 나오는 경우의 수는 위의 그림과 같습니다.

마찬가지로 명우는 근우의 점수가 최대한 작아지는 선택을 해야한다는 사실을 염두해야합니다.

이것을 통해 점화식을 생각해보면 다음과 같습니다.

if(t == 1)
DP[l][r][t] = min(DP[l + 1][r][nt], DP[l][r - 1][nt]); //해당 배열은 근우의 점수이므로 Arr을 더하지 않습니다!!

점화식을 조금 디테일하게 쓴다면 이렇습니다.

DP : l에서 r까지 카드가 남았고 t라는 사람의 차례일때 근우가 가지고 있는 점수
D : 메모이제이션을 하기 위해 선언된 함수(코드참고)
Arr : i번째 카드의 점수
t : 0이면 근우,1이면 명우
nt : t라는 사람의 다음사람

if(t == 0)
DP[l][r][t] = max(D(l + 1, r, nt) + Arr[l], D(l, r - 1, nt) + Arr[r]);
else if(t == 1)
DP[l][r][t] = min(D(l + 1, r, nt), D(l, r - 1, nt));

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

const int INF = 0x3f3f3f3f3f3f3f3fLL;

int Arr[1000];
int DP[1000][1000][2];
int D(int l, int r, int t)
{
	if (l > r)
		return 0;
	if (DP[l][r][t] != INF)
		return DP[l][r][t];
	int nt = (t == 0);
	if (t == 0)
		DP[l][r][t] = max( D(l + 1, r, nt) + Arr[l], D(l, r - 1, nt) + Arr[r]);
	else
		DP[l][r][t] = min(D(l + 1, r, nt), D(l, r - 1, nt));
	return DP[l][r][t];
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	while (T--)
	{
		memset(DP, INF, sizeof(DP));
		int N;
		cin >> N;
		for (int i = 0; i < N; i++)
			cin >> Arr[i];

		cout << D(0, N - 1, 0) << endl;

	}
}

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.