[Java] 11062 - 카드 게임

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

11062번: 카드 게임

간만에 알고리즘에 대한 포스팅을 합니다.

이분 탐색을 하는것 처럼 left와 right의 범위를 줄여나가며 근우를 기준으로 최선의 선택을 하는 과정을 DP에 저장합니다.

 

가장 중요한 부분은 아무래도 이 부분이 아닐까 싶습니다.

 

if(flag){ // 근우 차례일 때 명우 카드에 뭘 더해야 최대값인지를 정해야 됨.
            return DP[left][right] = Math.max(map[left] + solution(left+1, right, false),
                    map[right] + solution(left, right-1, false));
        }else{ // DP에는 근우가 가질 수 있는 최선의 선택만이 저장되기 때문에
//명우 차례일 때는 min값을 가져야 한다.
            return DP[left][right] = Math.min(solution(left+1, right, true),
                    solution(left, right-1, true));
}

solution이라는 함수는

현재 뽑을 수 있는 카드 중에서 가장 왼쪽 값인 left, 가장 오른쪽 값인 right, 근우와 명우의 차례를 나타내는 flag값을 가지고 있습니다.

 

위 flag를 통해 근우와 명우의 차례를 구분하는데, DP에는 근우의 최선의 선택 값이 저장된다는 것을 꼭 생각해야 합니다.

따라서, 근우의 차례일 때는 근우는  맨 왼쪽 카드인 map[left], 맨 오른쪽 카드인 map[right]를 뽑을 수 있습니다.

근우가 맨 왼쪽 카드를 map[left]를 뽑는다면, 명우가 뽑을 수 있는 값은 이렇게 표현할 수 있겠네요. solution(left+1, right, false)

근우가 맨 오른쪽 카드를 map[right]를 뽑는다면, 명우가 뽑을 수 있는 값은 solution(left, right-1, false)과  같이 됩니다.

따라서 위 값들 중 가장 max값을 뽑으면 됩니다.

 

그럼 명우의 차례는 어떻게 뽑으면 될까요?

아까 'DP에는 근우의 최선의 선택 값이 저장된다' 고 했습니다. 그러니까 명우는 왼쪽을 뽑던, 오른쪽을 뽑던 최소값을 비교해서 선택하면 되겠죵?

 

한 DP의 값은 Solution이라는 함수에 의해 재귀적으로 결정됩니다. 따라서 이미 값이 결정된 값에 대해서는 기존에 결정된 값을 return하고 넘어가면 됩니다.

 

그럼...

전체 코드를 보여드리겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
/*
근우부터 시작
 */
public class Main {
    static int T, N;
    static int[] map;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        T = Integer.parseInt(br.readLine());
 
        for(int t=0;t<T;t++){
 
            N = Integer.parseInt(br.readLine());
            map = new int[N];
            DP = new int[N+1][N+1];
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++){
                map[i] = Integer.parseInt(st.nextToken());
            }
 
            //근우가 얻는 점수.. // 근우 먼저 시작.
            solution(0, N-1, true);
            System.out.println(DP[0][N-1]);
        }
 
    }
 
    public static int solution(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(map[left] + solution(left+1, right, false),
                    map[right] + solution(left, right-1, false));
        }else{ // DP에는 근우가 가질 수 있는 최선의 선택만이 저장되기 때문에//명우 차례일 때는 min값을 가져야 한다.            return DP[left][right] = Math.min(solution(left+1, right, true),
                    solution(left, right-1, true));
        }
    }
}
 

 

올만에 알고리즘 풀이를 하니 재밌네요.

그럼 20000