[BOJ] 백준 11062번 카드 게임 (Java)

#11062 카드 게임

난이도 : 골드 3

유형 : DP/ 게임 이론

11062번: 카드 게임

▸ 문제

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

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

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

▸ 입력

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

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

▸ 출력

각 테스트케이스마다 근우와 명우가 최선의 전략으로 임할 때 근우가 얻게되는 점수를 줄로 구분하여 출력한다.

 

 

문제 풀이

카드게임 최선의 전략 문제로 근우의 입장에서 최대의 점수를 얻도록 설계해야한다. 일단 N개의 카드에서 0개의 카드로 흘러가는 구조이므로 Top-down 하향식 풀이로 접근을 했다. 

 

✔︎ 조건

  ∙ 카드의 수 N개

  ∙ 순서 : 근우(선) → 명우

  ∙ 최선의 전략으로 카드 선택

      ∙  가장 왼쪽 뽑기

      ∙  가장 오른쪽 뽑기

 

근우의 입장에서 생각해보면 근우는 최대의 값을 얻어야하고 명우는 최소의 값을 얻도록 전략을 세워야 한다.

 

위에서부터 아래로 내려가야 하는 구조이므로 재귀호출 방식을 쓰면 될 것 같다.

1. 왼쪽의 카드를 뽑을 경우
2.  오른쪽의 카드를 뽑을 경우

위의 두 케이스를 체크해서 그 중 max를 골라 리턴하는 방식으로 재귀를 사용했다.

static int solve(int left, int right, boolean flag) {

	// 게임이 종료됨을 뜻한다 [ 0(left) 1 2 .... n-2 n-1(right) ]
	if(left> right) return 0;

	if(dp[left][right] != 0) return dp[left][right];
		
	if(flag) { // 나
		return dp[left][right] = Math.max(card[left] + solve(left+1, right, false),
                                                   card[right] + solve(left, right-1, false));
	}else { // 상대방 
		return dp[left][right] = Math.min(solve(left+1, right, true),
                                                    solve(left, right-1, true));
	}
}

 

연습이니깐 차근차근 작은 케이스(예제)를 설계해 직접 뒤적뒤적해보자

4
1 2 5 2

 

true이면 근우(선) 차례이고 false이면 명우 차례이다.

 

최하위 문제까지 도달한 후에 다시 밑에서부터 올라오면서 해당 상황에서 근우(true) 최댓값을 골라서 dp[left][right]에 저장될 것이다. 반대로 명우(false)은 항상 최솟값만 골라서 저장될 것이다.

 

 if(left> right) return 0; 를 찍으면 다시 stack에 저장된 함수들이 호출되면서 두 케이스가 나온다.

  i) 1번 카드(2, 명우) → 2번 카드(5, 근우) → 3번 카드(1, 명우) → 0번 카드(1, 근우)

  ii) 1번 카드(2, 명우) → 2번 카드(5, 근우) → 0번 카드(1, 명우) → 3번 카드(1, 근우)

 

다시 케이스를 직접 살펴보면 위의 과정과 똑같은 것을 알 수 있다.

  i) 근우 : 카드 0 vs 카드 3  (1 vs 1) 둘 다 선택 가능

    if 근우가 0카드 선택  

    ii-1) 명우 : 카드 1 vs 카드 3 (2 vs 1) 카드 3 선택 

      iii) 근우 : 카드 1 vs 카드 2 (2 vs 5) 카드 2 선택

        iv) 명우 : 카드 1 선택

 

    if 근우가 3카드 선택

    ii-2) 명우 : 카드 0 vs 카드 2 (1 vs 2) 카드 0 선택 

      iii) 근우 : 카드 1 vs 카드 2 (2 vs 5) 카드 2 선택

        iv) 명우 : 카드 1 선택

  

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] card;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int i=0; i<t; i++) {
			int n = Integer.parseInt(br.readLine());
			card = new int[n];
			dp = new int[n+1][n+1];
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				int num = Integer.parseInt(st.nextToken());
				card[j] = num;
				
			}
			
			solve(0, n-1, true);
			System.out.println(dp[0][n-1]);
		}
	}
	
	
	static int solve(int left, int right, boolean flag) {
		
		if(left> right) return 0;
		if(dp[left][right] != 0) return dp[left][right];
		
		if(flag) {
			return dp[left][right] = Math.max(card[left] + solve(left+1, right, false),
											card[right] + solve(left, right-1, false));
		}else {
			return dp[left][right] = Math.min(solve(left+1, right, true), solve(left, right-1, true));
		}
		
	}
}