[백준] 11062-카드 게임(C++)

문제링크:www.acmicpc.net/problem/11062

11062번: 카드 게임

 

근우와 명우가 돌아가면서 최선의 선택을 한다.

 

처음에 규칙성을 찾아보려고 했지만, 규칙성을 찾지를 못했습니다.

1 8 100 2 10 이나 1 8 10 200 10 와 같은 다양한 경우에 따라서 예외가 발생하기 때문에 규칙성이 아닌

모든 경우를 생각해보는 것으로 생각을 바꿨습니다.

 

근데 모든 경우를 항상 계산해주는것이 아니라 이미 계산한 내용이라면 비트마스킹을 통해 저장해두었다가 다시 전달하는 형태로 구현하는 것이 핵심입니다. 

 

dp[1001][1001][2] ->   앞에 두 1001은 1~1000까지 시작점, 끝점을 나타냅니다. 그리고 마지막 2는 0일때는 근우 1일때는 명우의 턴을 가르킵니다. 

 

재귀함수 호출 코드입니다. DP up-down 방식 

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}

turn이 0일때는 근우 1일때는 명우의 차례입니다. 이 과정을 통해서 최종 결과값을 도출합니다. 

 

 

 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


int dp[1001][1001][2];
int t,n;
int arr[1001];

int solved(int startt, int endd, int turnn) {

	if (dp[startt][endd][turnn] != -1)
		return dp[startt][endd][turnn];

	if (startt == endd) {
		if (turnn == 1)
			return 0;
		else {
			return arr[startt];
		}
	}

	if (turnn == 0) {
		dp[startt][endd][turnn] = max((solved(startt + 1, endd, !turnn) + arr[startt]), (solved(startt, endd - 1, !turnn) + arr[endd]));
	}
	else {
		dp[startt][endd][turnn] = min((solved(startt + 1, endd, !turnn)), (solved(startt, endd - 1, !turnn) ));
	}

	return dp[startt][endd][turnn];
}


int main() {
	cin >> t;



	while (t--) {
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> arr[i];

		memset(dp, -1, sizeof(dp));

		
		cout << solved(1, n, 0)<<endl;// 0 is 근우 , 1 is 명우
		
	}


}