[백준 - 11062][Gold 3][해설 X] - 카드 게임 (JAVA)

문제 링크

---

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

 

문제

---

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

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

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

 

입력

---

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

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

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
/*
 *
 * 걸린시간 : 2시간
 *
 * N = 4
 *
 * 근우가 1~4에서 얻을 수 있는 최대 점수 = max(명우가 2~3에서 얻을 수 있는 최대 점수를 제외한 모든 2~4까지의 점수 + num[1],
 *                                         명우가 1~3에서 억을 수 있는 최대 점수를 제외한 모든 1~3까지의 점수 + num[4]
 *
 * 이를 점화식으로 표현하면 다음과 같다
 *
 * 최대 점수[근우][시작 번호][끝 번호] = max(누적합[시작 번호+1][끝번호] - 최대 점수[명우][시작 번호+1][끝 번호] + num[시작번호],
 *                                       누적합[시작 번호][끝번호-1] - 최대 점수[명우][시작 번호][끝 번호-1] + num[끝번호]
 * 최대 점수[명우][시작 번호][끝 번호] = max(누적합[시작 번호+1][끝번호] - 최대 점수[근우][시작 번호+1][끝 번호] + num[시작번호],
 *                                       누적합[시작 번호][끝번호-1] - 최대 점수[근우][시작 번호][끝 번호-1] + num[끝번호]
 * */
public class Main {
    static int[][][]dp; //[근우 : 0, 명우 : 1][시작번호][끝번호]
    static int[] card;
    static int[] sum;  //누적합

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for(int testcase=1;testcase<=T;testcase++){
            int N = Integer.parseInt(br.readLine());

            card = new int[N+1];
            dp = new int[2][N+1][N+1];
            sum = new int[N+1];

            StringTokenizer st = new StringTokenizer(br.readLine());

            //누적합 및 가드 값 저장
            for(int i=1;i<=N;i++){
                card[i] = Integer.parseInt(st.nextToken());
                sum[i] = card[i] + sum[i-1];
            }

            int max = getMax(0,1,N);
            System.out.println(max);
        }
    }

    //범위의 최대값을 구하는 메소드
    public static int getMax(int people, int start, int end){
        //이미 값을 아는 경우
        if (dp[people][start][end] > 0){
            return dp[people][start][end];
        }
        //먹을 수 있는 카드가 1개인 경우
        else if(start == end){
            dp[people][start][end] = card[start];
            return dp[people][start][end];
        }
        //다음 사람이 최대한 먹을 수 있는 점수를 제외하고 나머지 점수를 먹는 경우
        //1. 첫번째 카드 고르기
        //2. 끝 카드 고르기
        dp[people][start][end] = Math.max(sum[end] - sum[start] - getMax((people+1)%2,start+1,end) + card[start]
                ,sum[end-1] - sum[start-1]  - getMax((people+1)%2,start,end-1) + card[end]);
        return dp[people][start][end];
    }
}

 

 

실행 결과

---

 

 

팁

---

• DP 문제는 점화식을 먼저 세우고 시작해야한다.
• 범위 문제는 시작과 끝을 잘 생각하자
• 주어진 규칙을 그대로 점화식을 표현해보자