[Java] 백준 #20159 (누적합)

📍 출처

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

📝 문제

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

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

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

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

⌨️ 입력

카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다.

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

🖨 출력

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

⌨️ 예제 입력

6
3 2 5 2 1 3

🖨 예제 출력

11

📚 내가 제출한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 상대편 카드 누적합
        int[] evenSum = new int[N / 2];
        // 내 카드 누적합
        int[] oddSum = new int[N / 2];
        int z = 2;

        // 첫 번째 카드 넣어줌
        oddSum[0] = Integer.parseInt(st.nextToken());
        evenSum[0] = Integer.parseInt(st.nextToken());

        // 카드가 2장일 때
        if(N == 2){
            System.out.print(Math.max(evenSum[0], oddSum[0]));
            return;
        }

        // 입력받은 카드를 내카드, 상대카드 누적합 구하기
        for (int i = 2; i < N; i++) {
            if (i % 2 == 0) {
                oddSum[i / 2] += oddSum[i - z] + Integer.parseInt(st.nextToken());
                z++;
            } else {
                evenSum[i / 2] += evenSum[i - z] + Integer.parseInt(st.nextToken());
            }
        }

        // 내 카드 시작할때 밑장
        int reuslt = evenSum[N / 2 - 1];

        // 내꺼 밑장빼기
        for (int i = 0; i < N / 2; i++) {
            int temp = 0;
            temp = oddSum[i] + (evenSum[N / 2 - 1] - evenSum[i]);
            if (temp > reuslt) {
                reuslt = temp;
            }
        }

        // 상대카드 처음할 때 밑장
        if (reuslt < oddSum[0] + evenSum[N / 2 - 2]) {
            reuslt = oddSum[0] + evenSum[N / 2 - 2];
        }

        // 너꺼 밑장빼기
        for (int i = 0; i < N / 2 - 1; i++) {
            int temp = 0;
            temp = evenSum[N / 2 - 2] - evenSum[i] + oddSum[i + 1];
            if (temp > reuslt) {
                reuslt = temp;
            }
        }
        System.out.print(reuslt);
    }
}

✏️ 내가 제출한 코드에 대한 설명

• 상대 카드와 내 카드의 누적합을 구함
• 밑장을 빼면 그 다음부터 카드가 서로 바뀌므로 그 시점부터 상대방 카드에 남은 인덱스까지 누적합을 더해줌