백준 11062번 카드게임

< 11062번 카드게임 - 마포 코딩박 >

사용한 알고리즘: DP


 일렬로 놓여있는 카드를 근우부터 시작하여 근우와 명우 두사람이 번갈아가며 뽑을 때, 근우가 얻을 수 있는 최대 점수를 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~9)
 'dp[a][b][1] : 카드 왼쪽 index: a, 오른쪽 indx b, 근우차례 일 때, 근우가 얻을 수 있는 최대 점수'
 'dp[a][b][0] : 카드 왼쪽 index: a, 오른쪽 indx b, 명우차례 일 때, 근우가 얻을 수 있는 최대 점수' 라고 설정하였습니다.

(2) (코드 11~28)
 dp 값을 구하는 함수를 만들었습니다. dp값은 근우가 얻을 수 있는 최대 점수임을 생각합니다.
 왼쪽 index: start, 오른쪽 index: last 상태로 남은 카드 상태에서,
 근우 차례일 때는 왼쪽, 오른쪽 중 하나를 근우가 얻고, 게임을 진행 했을 때 둘 중 '최대' 값이 dp값이고,
 명우 차례일 때는 왼쪽, 오른쪽 중 하나를 없애고, 게임을 진행 했을 때 둘 중 '최소'값이 dp값입니다.
 카드가 한장 남았을 때 (start==end) 가 기저값입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int T, N;
	int card[1000];
	// dp[a][b][1] : 카드 가장왼쪽 index: a , 카드 가장오른쪽 index: b 인 상태 근우차례
	// dp[a][b][0] : 카드 가장왼쪽 index: a , 카드 가장오른쪽 index: b 인 상태 명우차례
	// 일 때, '근우'가 얻을 수 있는 최대 점수 를 dp 에 저장.
	int dp[1000][1000][2];
	// knwoo = true : 근우 차례
	int choice(int start, int last, bool knwoo){
	int &ret = dp[start][last][knwoo];
	if(ret != -1) return ret;
	// 마지막장
	if(start == last){
	if(knwoo)
	return ret = card[start];
	else
	return ret = 0;
	}
	// 근우 차례에서는 왼쪽, 오른쪽 중 하나 '취하고' 게임 진행 했을 때 '최대'값.
	if(knwoo)
	return ret = max(choice(start+1,last,false)+card[start],choice(start,last-1,false)+card[last]);
	// 명우 차례에서는 왼쪽, 오른쪽 중 하나를 '없애고' 게임 진행 했을 때 '최소'값
	else
	return ret = min(choice(start+1,last,true),choice(start,last-1,true));
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	memset(dp,-1,sizeof(dp));
	cin >> N;
	if(N==1){
	int a;
	cin >> a;
	cout << a << '\n';
	}
	else{
	for (int i = 0; i < N; ++i)
	cin >> card[i];
	cout << choice(0,N-1,true) << '\n';
	}
	}
	return 0;
	}

view raw BOJ 11062.cpp hosted with ❤ by GitHub