[백준] 11062 카드 게임

문제

---

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.

 

 

 

 

 

풀이

---

3차원 dp 를 이용하여 문제를 풀었다.

 

근우의 값을 저장하여 전에 뽑은 값에 현재의 값을 더해 더 큰쪽을 선택하는 방식으로 풀었다.

 

명우는 현재 주어진 수중 작은 것을 뽑도록 하였다.

아래가 이 문제를 푸는 핵심 코드다.

static int findBest(int turn, int left, int right) {
	
	if(dp[turn][left][right] != -1) {
		return dp[turn][left][right];
	}
	
	
	if(left >= right) {
		if(turn == 0) {
			return arrNumber[left];
		}
		else {
			return 0;
		}
	}
	
	dp[turn][left][right] = 0;
	
	if(turn == 0) {
		dp[turn][left][right] = Math.max(findBest(turn + 1, left + 1, right) + arrNumber[left], findBest(turn + 1, left, right - 1) + arrNumber[right]);
	}
	else {
		dp[turn][left][right] = Math.min(findBest(turn - 1, left + 1, right), findBest(turn - 1, left, right - 1));
	}
	
	return dp[turn][left][right];
}

만약 left == right 가 된다면 현재 카드를 제외하고 뽑을 카드가 없다는 것이다. 이 때, 근우면 해당 카드의 값을 더해주어야 하기 때문에 return arrNumber[left] 를 해주는 것이고, 명우면 return 0  을 하여 카드를 뽑았으나 값은 더해주지 않게한다.

 

이렇게 명우의 경우에는 더 작은 결과가 나오는 것을 선택하게 하고

근우일 경우는 더 큰 결과가 나오는 것을 선택하게 하면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int[][][] dp;
	static int[] arrNumber;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		
		for(int i = 0 ; i < n ; i++) {
			int size = Integer.parseInt(bufferedReader.readLine());
			
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			arrNumber = new int[size + 1];
			
			for(int j = 1 ; j <= size ; j++) {				
				arrNumber[j] = parseInt(st.nextToken());
			}
			
			dp = new int[2][size + 1][size + 1];
			for(int turn = 0 ; turn < 2 ; turn++) {
				for(int j = 1 ; j <= size ; j++) {
					for(int k = 1 ; k <= size ; k++) {
						dp[turn][j][k] = -1;
					}
				}
			}
			
			
			sb.append(findBest(0, 1, size) + "\n");
		}
		
		System.out.println(sb);
	}
	
	static int parseInt(String number) {
		return Integer.parseInt(number);
	}
	
	static int findBest(int turn, int left, int right) {
		
		if(dp[turn][left][right] != -1) {
			return dp[turn][left][right];
		}
		
		
		if(left >= right) {
			if(turn == 0) {
				return arrNumber[left];
			}
			else {
				return 0;
			}
		}
		
		dp[turn][left][right] = 0;
		
		if(turn == 0) {
			dp[turn][left][right] = Math.max(findBest(turn + 1, left + 1, right) + arrNumber[left], findBest(turn + 1, left, right - 1) + arrNumber[right]);
		}
		else {
			dp[turn][left][right] = Math.min(findBest(turn - 1, left + 1, right), findBest(turn - 1, left, right - 1));
		}
		
		return dp[turn][left][right];
	}
}