[BOJ 11062] 카드 게임

https://www.acmicpc.net/problem/11062

11062번: 카드 게임

 

- 문제 요약

 

근우와 명우는 재미있는 카드 게임을 하고 있다.

N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다.

한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다.

턴은 근우부터 시작하고 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다.

게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다.

놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1 이상 10,000 이하다.

 

 

- 알고리즘 정리

 

재귀 DP로 해결할 수 있는 문제입니다.

DP[i][j] : i~j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수

위와 같이 정의를 하고, 문제에서는 근우가 얻는 점수를 구하라고 했으니 근우의 시점에서 점화식을 작성했습니다.

 

근우가 이기게 하려면 근우의 차례 때 점수를 최대로 하는 플레이를 해야 하고, 명우의 차례 때는 근우의 점수를 최소로 하는 플레이를 해야 합니다.

점화식을 짤 때 왼쪽 카드와 오른쪽 카드를 뽑은 경우를 나눠서 생각해 보겠습니다.

 

근우 : max(왼쪽_카드_값 + 왼쪽_카드_뽑았을_때, 오른쪽_카드_값 + 오른쪽_카드_뽑았을_때)

명우 : min(왼쪽_카드_뽑았을_때, 오른쪽_카드_뽑았을_때)

 

위와 같은 점화식을 활용해서 문제를 해결해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int t,n,arr[MAX],dp[MAX][MAX];

int f(int l,int r,int x){
	if(l>r){
		return 0;
	}
	if(dp[l][r]){
		return dp[l][r];
	}
	if(x%2){
		return dp[l][r]=max(arr[l]+f(l+1,r,x+1),arr[r]+f(l,r-1,x+1));
	}
	else{
		return dp[l][r]=min(f(l+1,r,x+1),f(l,r-1,x+1));
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--){
		memset(dp,0,sizeof(dp));
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		f(0,n-1,1);
		cout<<dp[0][n-1]<<'\n';
	}
}

코드 제출 결과