취수 게임 문제 풀이 보고서

원본 링크:
취수놀이
문제 해결 방법:
동적 기획을 활용하여 말미 상태에서 초기 상태를 역추하고 일부 바둑 결과에서 전체 바둑 결과를 역추한다.
코드:

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main()
{
	// dp[i][j][k]               , i          ，j          ，k      。
	int dp[100][100][2];
	int n = 0;
	assert(1 == scanf("%d", &n));
	memset(dp, 0, sizeof(dp));
	vector input;
	for (int i = 0; i < n; i++) {
		int tmp = 0;
		assert(1 == scanf("%d", &tmp));
		input.push_back(tmp);
	}
	int last = (n + 1) % 2; //         
	for (int i = 0; i < n; i++) {
		dp[i][i][last] = input[i];
		dp[i][i][last ? 0 : 1] = 0;
	}
	for (int i = 2; i <= n; i++) {
		last = last ? 0 : 1;
		for (int j = 0; i + j <= n; j++) {
			if (input[j] + dp[j + 1][i + j - 1][last] > input[i + j - 1] + dp[j][i + j - 2][last]) {
				dp[j][i + j - 1][last] = input[j] + dp[j + 1][i + j - 1][last];
				dp[j][i + j - 1][last ? 0 : 1] = dp[j + 1][i + j - 1][last ? 0 : 1];
			}
			else {
				dp[j][i + j - 1][last] = input[i + j - 1] + dp[j][i + j - 2][last];
				dp[j][i + j - 1][last ? 0 : 1] = dp[j][i + j - 2][last ? 0 : 1];
			}
		}
	}
	printf("%d %d
", dp[0][n - 1][0], dp[0][n - 1][1]);
	return 0;
}