[백준]11062 카드게임 #사선dp

https://blog.naver.com/ngoodsamari/221776557221

행렬곱셉순서와 비슷한 문제.

 

1. 풀이

(1) 단 두개가 남았을 때 부터 생각해서 N개의 카드가 있을 때 까지 확장한 후 최적의 선택을 찾는다.

(2) dp[i][j] : i~j를 뽑았을 때 근우가 얻을 수 있는 최대 점수

(3) 근우가 항상 먼저 뽑기 때문에 현재까지 뽑은 카드의 개수(N-(j-i+1))가 짝수이면 근우차례이고, 홀수이면 명우차례이다.

(4) 명우도 항상 최적의 선택을 하기 때문에, 명우차례일때는 근우입장에서 최소의값을 선택해야 한다.

​

2. 소스코드

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int L[1000];

// dp[i][j] : i~j를 뽑았을때 근우가 얻을 수 있는 최대 점수
int dp[1001][1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;
	for (int a = 0; a < t; a++) {
		int N;
		cin >> N;
		memset(dp, 0, sizeof(dp));

		for (int i = 1; i <= N; i++) {
			cin >> L[i];
			if (N % 2 == 1) {
				dp[i][i] = L[i];
			}
		}

		for (int l = 1; l < N; l++) {
			for (int i = 1; i <= N - l; i++) {
				int j = i + l;

				// 근우차례
				if ((N - (j - i + 1)) % 2 == 0) {
					dp[i][j] = max(dp[i + 1][j] + L[i], dp[i][j - 1] + L[j]);
				}
				// 명우차례
				else {
					dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
				}

			}
		}
		cout << dp[1][N] << "\n";
	}

	return 0;
}