백준 20159 (동작 그만. 밑장 빼기냐?) - java

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

 

문제

싸늘하다. 정훈이는 다음과 같은 도박을 하고 있다.

N개의 카드와 2명의 플레이어가 있다. 플레이어가 자신과 상대방에게 번갈아 가며 카드의 윗장부터 한 장씩 분배한다. 단, 카드는 분배한 사람부터 받는다. 카드를 모두 분배했을 때 카드에 적힌 수의 합이 더 큰 사람이 이긴다. 두 명이 공평하게 카드를 나눠 갖기 위해 카드의 개수는 짝수로 주어진다.

카드를 섞고 있는 정훈이는 타짜다. 수없이 많이 카드를 섞어본 경험으로 섞고 난 후 카드의 값들을 다 알고 있다. 정훈이에게 카드를 분배할 수 있는 기회가 왔다. 확실한 승리를 위해 카드를 분배할 때 카드의 윗장이 아닌 밑장을 빼는 밑장 빼기를 하기로 마음을 먹었다. 상대는 눈치가 빠르기로 유명한 선수이므로 밑장 빼기는 최대 한번 할 것이다.

정훈이가 최대 한번 밑장 빼기를 할 때 얻을 수 있는 최대 카드의 합을 구하여라.

 

유형 : 누적합

 

접근 방식

• 1 - 3 - 5 - ..... , 2 - 4 -6 - ...... 순으로의 누적합을 구한다
• 밑장빼기를 하지 않을 경우의 값을 구하고 밑장빼기를 했을 때의 값을 비교한다
• (홀수 번째에 밑장빼기를 한 경우)
  • tmp = sum[i-2] + (sum[n] - sum[i-1])
• (짝수 번째에 밑장빼기를 한 경우)
  • tmp = sum[i-1] + (sum[n-2] - sum[i-2])

 

코드

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

public class BOJ_20159_동작_그만_밑장_빼기냐 {

    static int n;
    static int[] arr;
    static int[] sum;

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

        n = Integer.parseInt(st.nextToken());

        arr = new int[n+1];
        sum = new int[n+1];

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        sum[1] = arr[1];

        for(int i = 2 ; i <= n ; i++) {
            sum[i] = arr[i] + sum[i - 2];
        }


        int max = sum[n - 1];

        for(int i= 1 ; i <= n ; i++) {

            int tmpV = 0;

            if(i % 2 == 1) {
                // my turn
                tmpV = i - 2 < 0 ? 0 : sum[i-2];
                tmpV += sum[n] - sum[i-1];
            }else {
                tmpV = sum[i-1];
                tmpV += sum[n-2] - sum[i-2];
            }

            max = Math.max(max,tmpV);
        }

        System.out.println(max);
        br.close();
    }

    static void print() {
        for(int i = 1 ; i <= n ; i++) {
            System.out.print(sum[i]+" ");
        }
        System.out.println();
    }
}