[백준] 11062 - 카드게임

[문제링크]

11062번: 카드 게임

 

0. 번갈아가며 양쪽 끝에서 한장씩 집을때 최대한 많은 점수를 얻는 방법

 

1. x~y까지의 카드에서 최대한 많은 점수를 얻으려면 card[y] + (x~y-1) 혹은 card[x] + (x+1~y)중 큰 값으로 고를 수 있다

 

2. 이때, 각자 서로의 점수를 위해 최선의 전략을 사용하고, 서로 가져갈수 있는 카드의 총합은 동일하다

• 따라서, 후 플레이어의 최선의 전략 = 선 플레이어의 점수를 가능한 낮추는 전략 과 같다

 

3. DP테이블을 2중으로 만들어, (x, y) 만큼의 카드 상태에서 선 플레이어/후 플레이어 각각의 최선의 결과를 저장한다

• 후 플레이어의 선택은 선 플레이어의 점수와는 관계없으므로 저장하지 않는다

 

4. 모든 테이블이 완성된 후, 모든 카드에 대해 선 플레이어의 점수를 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			int N = pint(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] card = new int[N];
			int[][][]dp = new int[N+1][N+1][2];
			
			for (int i = 0; i < N; i++) {
				card[i]=pint(st.nextToken());
			}
			
			for (int i = 0; i < N; i++) {
				dp[i][i][0]=card[i];
				dp[i][i][1]=0;
			}
			
			//i~i+len 까지의 카드를 고려했을때, 근우가 얻을수 있는 최대 점수
			for (int len = 1; len < N; len++) {
				
				for (int i = 0; i < N-len; i++) {
					//i : 시작점, len : 길이
					int j = i+len;
					//근우턴일때 근우 최대점수 = 왼/오 각 경우중 최댓값 + 카드 선택값
					dp[i][j][0]=Math.max(card[j]+dp[i][j-1][1], card[i]+dp[i+1][j][1]);
					//명우턴일때 근우 최대점수 = 왼/오 각 경우중 최솟값 (카드 선택 못함)
					dp[i][j][1]=Math.min(dp[i+1][j][0], dp[i][j-1][0]);
				}
			}
			System.out.println(dp[0][N-1][0]);			
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면