[백준 - 20159][GOLD 4][해설 X] - 동작 그만. 밑장 빼기냐? (JAVA)

 

문제 링크

---

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

 

문제

---

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

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

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

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

 

입력

---

• 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다.
• 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다.

 

출력

---

정훈이가 얻을 수 있는 최대 카드 값의 합을 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int N = Integer.parseInt(br.readLine());
        int[] cards = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        long[] preEven = new long[N/2];
        long[] preOdd = new long[N/2];

        preOdd[0] = cards[0];
        preEven[0] = cards[1];

        for(int i=2;i<N;i+=2){
            preOdd[i/2] = preOdd[i/2-1] + cards[i];
            preEven[i/2] = preEven[i/2-1] + cards[i+1];
        }

        //밑장빼기를 안한경우와 처음부터 밑장빼기를 해서 내가 먹은 경우중 큰 값으로 초기화
        long max = Math.max(preOdd[preOdd.length-1],preEven[preEven.length-1]);
        //밑장빼기를 해서 상대가 먹은 경우를 생각해서 초기화
        max = Math.max(max,cards[0] + preEven[preEven.length-1] - cards[cards.length-1]);

        for(int i=2;i<N;i+=2){
            max = Math.max(max,preOdd[i/2-1] + preEven[preEven.length-1] - preEven[i/2-1]); //밑장을 내가 먹은경우
            max = Math.max(max,preOdd[i/2] + preEven[preEven.length-1] - preEven[i/2-1] - cards[cards.length-1]); //밑장을 상대가 먹은경우
        }

        System.out.println(max);
    }
}

 

 

실행 결과

---

 

팁

---

• 밑장빼기는 나한테도, 상대한테도 줄 수 있다.
• 홀수번째와 짝수번째의 누적합을 나누어서 해결하면 쉽다.