BOJ 20159, 동작 그만 밑장 빼기냐?

시간 복잡도를 줄여야하는 문제

아이디어를 찾아서 해결 해야하는 문제

꼭 손으로 그려보면서 규칙성을 찾기

문제를 보고 처음에는 각 차례에서 밑장빼기를 하는 경우를 재귀로 구현하여 풀어보면 어떨지 생각했다.

하지만 주어진 N의 범위는 10만.

 

따라서 모든 경우의 수를 재귀로 구현하면 시간복잡도는 O(N^2)이 된다.

(N개 중 밑장빼기를 할 index 찾기 * 원소 순회하면서 누적합 계산)

O(N) * O(N)

 

따라서 시간복잡도를 줄여야 했고, 다른 방법을 생각하게 되었다.

 

이렇게 아이디어를 필요로 하는 문제들을 푸는 과정은 직접 손으로 그려라!!

밑장 빼기 하는 숫자는 맨 마지막 원소이므로 고정.

밑장 빼기를 하면 맨 마지막 원소를 다른 index에 삽입하여

홀수번째/짝수번째 index를 나눠서 누적합을 구하는 것으로 생각할 수 있었다.

 

a1

a2

a3

a4

a5

 

위와 같은 순서로 원소가 있을 때,

홀수번째 누적합 S(odd) = a1 + a3 + a5

짝수번째 누적합 S(even) = a2 + a4

 

a5를 왼쪽으로 한칸씩 이동시키면

a1

a2

a3

a5

a4

S(odd) = a1 + a3 + a4

S(even) = a2 + a5

즉, S(odd) = S(odd) - a5 + a4 가 되고,  S(even) = S(even) + a4 - a5가 된다.

 

같은 방법으로 한 칸 더 왼쪽으로 이동시키면

a1

a2

a5

a3

a4

 

S(odd) = a1 + a5 + a4

S(even) = a2 + a3

S(odd) = S(odd) - a3 + a5 가 되고,  S(even) = S(even) + a3 - a5가 된다.

 

즉 마지막 원소를 왼쪽으로 한 칸씩 옮길 때마다 (+ i의 짝수/홀수에 따라)

S(odd) = S(odd) - a[i] + a[last]

또는

S(odd) = S(odd) + a[i] - a[last]

가 되는 것을 발견할 수 있다.

 

이 값중 최댓값을 반환하면 되는 문제!

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

public class 밑장빼기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.stream(arr).forEach(num -> deque.addLast(num));
        int ans = solve(arr);
        System.out.println(ans);
    }

    static int solve(int[] arr){
        int originEvenSum = 0;
        for(int i=0; i<arr.length; i++){
            if(i % 2 == 0){
                originEvenSum += arr[i];
            }
        }
        int ans = originEvenSum;
        int last = arr[arr.length - 1];
        for(int i = arr.length - 2; i >= 0; i--){
            if(i % 2 == 1)
                originEvenSum = originEvenSum - last + arr[i];
            else
                originEvenSum = originEvenSum - arr[i] + last;
            ans = Math.max(ans, originEvenSum);
        }
        return ans;
    }
}