백준 20159 동작 그만. 밑장 빼기냐?

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

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

문제

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

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

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

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

입력

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

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

출력

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

알고리즘 분류

• 누적 합

풀이

문제를 잘~ 이해하자..!

핵심은 밑장 빼기다! 밑장 빼기를 시전하는 것은 리스트의 가장 뒤 카드를 소비하는 것임을 명심!

그리고 밑장 빼기는 내 턴 뿐만 아니라 상대 턴에도 할 수 있다.

이제 문제를 풀어보자.

우선 밑장 빼기가 없다고 생각해 보자.

나부터 카드를 받게 되니 나는

3 2 5 2 1 3

3,5,1 카드를 받게 된다.

밑장 빼기를 한다면? 언제 할 건지도 생각해야 한다. 우선 3번째 카드와 4번째 카드에서 밑장 빼기를 해보자.

3 2 5 2 1 3

3 2 5 2 1 3

기존에 짝수 인덱스의 카드를 받다가 밑장 빼기를 한다면 밑장 빼기를 한 인덱스부터 홀수 인덱스의 카드를 받는 것을 알 수 있다.

따라서 우리는 짝수 인덱스의 누적 합 (evenSum), 홀수 인덱스의 누적 합 (OddSum)을 구해놓고, 0~5번 인덱스 모두 밑장 빼기를 해보며 최대 값을 구하면 된다.

그럼 최종적으로 시간 복잡도는 O(N)

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()) {

    //input
    val n = getInt()
    val list = getIntList()
    val oddSum = IntArray(list.size)
    val evenSum = IntArray(list.size)

    for (i in list.indices) {
        if (i and 1 == 0) {
            if (i - 2 >= 0) {
                evenSum[i] = evenSum[i - 2] + list[i]
            } else {
                evenSum[i] = list[i]
            }
        } else {
            if (i - 2 >= 0) {
                oddSum[i] = oddSum[i - 2] + list[i]
            } else {
                oddSum[i] = list[i]
            }
        }
    }
    //solve
    var answer = 0
    for (i in list.indices) {
        var sum = 0
        if(i and 1 == 0){ // 내 턴에 밑장 빼기
            sum += if (i >= 2) evenSum[i - 2] else 0
            sum += if(i>=2) (oddSum[n-1] - oddSum[i-1]) else oddSum[n-1]
        }
        else{
            //상대 턴에 밑장 빼기
            sum += if(i>=2)oddSum[n-1]-oddSum[i-2] - list[n-1] else oddSum[n-1] - list[n-1]
            sum += evenSum[i-1]
        }
        answer = answer.coerceAtLeast(sum)
    }
    write("$answer")
    close()
}