# Card Game

# 문제

 

# 입력 및 출력

 

# 풀이

처음에 풀 땐 dp[i][j]를 만들어서 i부터 j까지의 카드중에서 맨 앞과 맨 뒤 중 어떤 값을 선택할지를 dp에 저장해뒀었다.

근데 이렇게 하면 문제점이 가장 큰 값을 선택하기 때문에 앞에 작은 값이 오더라도 계산 결과는 크게 나오는 경우를 처리하지 못했다.

 

// 틀린 코드
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("card.inp");
ofstream fout("card.out");

int card[1000];
pair<int, int> dp[1000][1000];

int cal_sum(int n, int fb) {
	int s, e, sum;
	if (fb == 0) {
		s = 1;
		e = n - 1;
		sum = card[0];
	}
	else {
		s = 0;
		e = n - 2;
		sum = card[n - 1];
	}
	int time = 0;
	while (1) {
		int num = dp[s][e].first;
		int fb = dp[s][e].second;
		if (time == n - 1) break;
		if (time % 2 == 1) sum += num;
		time++;
		if (fb == 0) s++;
		else e--;
	}
	return sum;
}

int main() {
	int T, n;
	fin >> T;
	while (T--) {
		fin >> n;
		for (int i = 0; i < n; i++) {
			fin >> card[i];
			dp[i][i] = make_pair(card[i], 0);
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (card[i] == card[j]) {
					dp[i][j] = card[i + 1] < card[j - 1] ? make_pair(card[i], 0) : make_pair(card[j], 1);
					continue;
				}
				if (card[i] > card[j]) {
					dp[i][j] = make_pair(card[i], 0);
				}
				else {
					dp[i][j] = make_pair(card[j], 1);
				}
			}
		}

		int front = cal_sum(n, 0);
		int back = cal_sum(n, 1);

		fout << max(front, back) << "\n";
	}
}

 

그래서 재귀적으로 작은 쪽부터 돌면서 계산 결과가 가장 크게 나오는 것을 찾도록 했다.

 

#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("card.inp");
ofstream fout("card.out");

int card[1001];
int dp[1001][1001];

int cal_sum(int start, int end, bool turn) {
	if (start > end) return 0; // 확인 범위 초과시 종료
	if (dp[start][end]) return dp[start][end]; // 중복계산 막기 위해 설정
	
	int choice_front = cal_sum(start + 1, end, !turn);
	int choice_back = cal_sum(start, end - 1, !turn);

	if (turn) { // Alice 턴일 경우
		choice_front += card[start]; // 맨 앞 선택
		choice_back += card[end]; // 맨 뒤 선택
		return dp[start][end] = max(choice_front, choice_back); // 계산 결과 큰 것 선택
	} 
	else { // Computer 턴의 경우
    	// DP 배열은 Alice 경우만 생각하기 때문에 따로 선택된 카드 값을 더해주지 않음
        // 하지만 나중에 계산할 때 필요하기 때문에 DP에 저장해둠
        // Computer가 가장 작은 값을 선택하도록 만들었다고 생각하기
		return dp[start][end] = min(choice_front, choice_back); 
	}

}

void clear(int n) { // dp배열 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dp[i][j] = 0;
		}
	}
}

int main() {
	int T, n;
	fin >> T;
	while (T--) {
		fin >> n;
		for (int i = 0; i < n; i++) {
			fin >> card[i];
		}
		fout << cal_sum(0, n - 1, true) << "\n";
		clear(n);
	}
}

 

표면상으로만 확인하지 말고 계속해서 확인해야하는 부분이라면 재귀적으로 확인하도록..!

 

 

dp는 너무너무 어렵다.. 아직도 이해가 잘 안간다..

어떻게 푼거지ㅋㅋ