백준 20159 자바 - 동작 그만. 밑장 빼기냐? (BOJ 20159 JAVA)

문제 : boj20159

 

 

1. 정훈이가 받을 차례에 밑장빼기 한 경우

  기본 아이디어는 직접 밑장빼기를 할 때 어떤 카드를 주게되는지 그려보면서 해보면 어렵지 않게 찾을 수 있다. 예제 입력 1 (3 2 5 2 1 3)을 홀수번째 카드(원래 정훈이가 받을 카드)와 짝수번째 카드(원래 상대방이 받을 카드)로 나눠서 그려보자. 

그럼 밑장빼기를 하지 않는다면 다음과 같이 3, 5, 1을 받게 된다.

그럼 5번을 받을 차례 때 밑장빼기를 하면 어떻게 될까? '5'를 받을 차례에 짝수번째의 마지막에 있는 '3'을 받고, 이후 순서가 변경되면서 짝수번째를 정훈이가 받게 된다. 따라서 밑장빼기를 한 이후로는 짝수번째 카드를 받게 된다.

이런식으로 모든 경우를 다 그려보면 다음과 같다.

 

 

2. 정훈이가 상대방한테 밑장을 빼서 주는 경우

  로직적으로 맞다고 생각했는데 자꾸 틀렸다고 나왔다. 맞왜틀을 외치다가 생각해보니 밑장빼기를 상대방한테 카드를 줄 때도 할 수 있음을 깨달았다. 사실 제한 안걸었으니 당연히 되는건데 왜 생각을 처음부터 못했는지 모르겠다.

 

  이 경우에 해당하는 모두를 그려보겠다. 우선 정훈이 첫장은 무조건 받게된다. 그리고 상대방 차례 때 밑장을 빼서 주게 되면, 그 이후 짝수번째의 처음 카드부터 정훈이가 받아야 한다. 따라서 '1'의 경우에서 짝수쪽에 받게되는게 좌측으로 한칸 밀려서 받으면 된다.

 

 

3. '1'과 '2'를 빠르게 계산하기 위한 방법

  홀수번째와 짝수번째 모두 끊기지 않는 구간에 대한 합만 구할 수 있으면 된다. 따라서 홀수와 짝수번째로 입력된 값에 대해 각각 누적합 배열을 만들어두면 O(1)로 바로 구할 수 있다.

최종적으로 시간복잡도는 '입력받기 O(N) + N개만큼 다시 보면서 모든 경우 중 최대값 찾기 O(N) = O(N)'이 된다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    int n;
    int[] oddPrefixSum, evenPrefixSum;

    private int getOddPrefixSumUntil(int until) {
        return oddPrefixSum[until];
    }

    private int getEvenPrefixSumFrom(int from) {
        return evenPrefixSum[n/2] - evenPrefixSum[from];
    }

    private void solution() throws Exception {
        n = nextInt();
        oddPrefixSum = new int[n/2+1];
        evenPrefixSum = new int[n/2+1];
        for (int i = 1; i <= n/2; i++) {
            oddPrefixSum[i] = oddPrefixSum[i-1] + nextInt();
            evenPrefixSum[i] = evenPrefixSum[i-1] + nextInt();
        }

        int answer = 0;
        int lastEvenCard = getEvenPrefixSumFrom(n/2-1);
        for (int i = 0; i <= n/2; i++) {
            int odd = getOddPrefixSumUntil(i);
            int even = getEvenPrefixSumFrom(i);
            if (i != 0) {
                even = Math.max(even, getEvenPrefixSumFrom(i-1)-lastEvenCard);
            }

            int sum = odd+even;
            if (answer < sum)
                answer = sum;
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}