[BOJ] 20159 - 동작 그만. 밑장 빼기냐?

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/20159

20159번: 동작 그만. 밑장 빼기냐?

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. 우선 밑장을 한 번 빼고 나면, 해당 카드로부터 앞으로 정훈이가 받았어야 할 카드와 상대방이 받았어야 할 카드가 뒤바뀌게 됩니다.

 

문제를 해결하기 위해 두 개의 배열을 이용합니다. 하나는 해당 카드까지 정훈이 또는 상대방이 받은 카드의 점수 합을, 나머지 하나는 해당 카드로부터 끝까지 정훈이 또는 상대방이 받을 수 있는 카드의 점수 합을 저장합니다.

 

이렇게 두 개의 배열을 만들어 둔 뒤, 카드를 첫 장부터 분배하며, 해당 카드의 순서에 밑장을 빼게 되면 정훈이가 몇 점을 얻을 수 있는지를 계산하여 가장 큰 값을 출력합니다.

 

마지막 유의해야 할 점은, 밑장을 빼지 않았을 때의 경우도 고려해주어야 한다는 것입니다.

 

import java.io.*;
import java.util.*;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int []arr = new int[N];
        int []dp = new int[N];
        int []dp2 = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[N-1] = arr[N-1];
        dp[N-2] = arr[N-2];
        for (int i = N-3; i>=0; i--) {
            dp[i] = dp[i+2]+arr[i];
       } // 해당 카드로부터 끝까지 얻을 수 있는 점수
 
        dp2[0] = arr[0];
        dp2[1] = arr[1];
        for (int i = 2; i < N; i++) {
            dp2[i] = dp2[i-2]+arr[i];
       } // 해당카드까지 얻은 점수
 
        long max = Math.max(dp[1],arr[0]+dp[1]-arr[N-1]); // 첫 장과 두 번째 장에서 밑장빼기를 한 경우
 
        for (int i = 2; i < N; i++) { // 3번째 장부터 확인
            if(i%2==0){ // 정훈이의 턴에 밑장 빼기
                max = Math.max(max, dp2[i-2] + dp[i+1]);
            }
            else{ // 상대의 턴에 밑장 빼기
                max = Math.max(max, dp2[i-1] + dp[i]-arr[N-1]);
            }
        }
        long sum = dp[0];
        max = Math.max(sum,max);
 
        bw.write(String.valueOf(max)+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
}