백준 11062 카드게임

백준 11062 카드게임

solve(i,j)는 

i에서 j까지의 카드(i와j는 인덱스)만 남았을 때,

""지금 상황에서"" <<중요

근우가 먹을 수 있는 최대 점수

이다.

i에서 j까지의 카드가 남았을 때 

근우와 명우는 여러가지의 점수를 가지고 있을 수 있다

예를 들어

1 2 5 2 의 경우

중간에 2개의 카드인 2와 5만 남았을 때

근우와 명우가 1 : 2일수도 있고, 2 : 1 일수도 있다.

하지만 중요한건 2 5 만 남았을 때

그 이후로 근우와 명우가 먹을 최적의 점수는 언제나 같다는 점이다

따라서 이를 이용하여 DP로 풀면 된다

DP[i][j] = (if 근우턴) max(DP[i+1][j] + card[i] , DP[i][j - 1] + card[j])

(if 명우턴) min(DP[i+1][j], DP[i][j-1])

명우턴에서 저런 연산을 하는 이유는

명우입장에서 '본인이 큰 점수를 먹는다'는 것은 '근우가 작은 점수를 먹는다' 이기 때문이다.

그리고 그때 card[i]나 card[j]를 더해서 계산하지 않는 이유는

DP의 값은 '근우가 가질수 있는 최대 점수' 이지, '명우가 가질 수 있는 최대 점수' 가 아니기 때문이다.

명우턴에서는 명우가 먹지 근우가 먹는게 아니기 때문에 DP에 먹은 카드를 더해서 넣지 않는다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stack>
#include <tuple>

using namespace std;

int testcase;
int N;
int card[1001];
int memo[1001][1001][2];
int cardMax;

//turn 이 트루면 근우턴
int solve(int start, int end, bool turn) {
	int & ret = memo[start][end][turn];
	if (ret != -1) return ret;

	if (start >= end) {
		if (turn) return ret = card[start];
		else return ret = 0;
	}

	if (turn) {
		ret = max((solve(start + 1, end, !turn) + card[start]), (solve(start, end - 1, !turn) + card[end]));
	}
	else {
		ret = min((solve(start + 1, end, !turn)), (solve(start, end - 1, !turn)));
	}


	return ret;
}

int main() {
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &N);
		cardMax = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d", &card[i]);
			cardMax += card[i];
		}


		for (int i = 0; i < 1001; i++) {
			for (int j = 0; j < 1001; j++) {
				for (int k = 0; k < 2; k++) {
					memo[i][j][k] = -1;
				}
			}
		}

		int a = 0, b = 0;
		printf("%d\n", solve(0, N - 1, true));
	}

	return 0;
}

처음에 위와같이 풀어서 맞았는데,

생각해보니 남은 카드가 있으면 명우와 근우의 턴은 정해져있다.

예를들어 총 5장의 카드 중 3장이 남았으면 근우와 명우 한턴씩 한것이므로 근우의 턴이고

11장의 경우 5장이 남았으면 마찬가지로 근우의 턴 등등.. 

남은카드가 짝수면 명우 턴, 아니면 근우 턴이므로 

solve의 인자로 turn도 넘겨주지 않고

DP에서도 turn을 메모이제이션 하지 않아도 되고,

dp의 초기값을 0으로 해도 되므로(왜냐하면 카드의 값은 전부 1 이상이기 때문에)

memset으로 초기화하여서 시간을 줄일수 있게 된다.

따라서 아래와 같은 코드로 시간을 절반 이상 줄일수 있다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string.h>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stack>
#include <tuple>

using namespace std;

int testcase;
int N;
int card[1001];
int memo[1001][1001];

// solve(i,j)는 i~j까지의 카드만 남았을 때, ""지금 상황에서"" 내가 먹을 수 있는 최대의 점수
int solve(int start, int end) { 
	int & ret = memo[start][end];
	if (ret != 0) return ret;

	if (start >= end) {
		if ((N - (start + end)) % 2) return ret = card[start];
		else return ret = 0;
	}

	if ((N - (start + end)) % 2){
		ret = max((solve(start + 1, end) + card[start]), (solve(start, end - 1) + card[end]));
	}
	else {
		ret = min((solve(start + 1, end)), (solve(start, end - 1)));
	}


	return ret;
}

int main() {
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			scanf("%d", &card[i]);
		}
		
		for (int i = 0; i < N; i++) {
			memset(memo[i], 0, sizeof(int) * N);
		}

		printf("%d\n", solve(0, N - 1));
	}

	return 0;
}