[BOJ] 20159. 동작 그만. 밑장 빼기냐?(DP).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이 문제를 해결하기 위해 생각보다 많은 시간을 고민한 것 같다...

우선 N의 범위는 N (2 ≤ N ≤ 100,000)

Naive 하게 접근하면 O(N^2)로 TLE가 발생한다.

//

누적합 + DP 를 활용해서 O(N)만에 해결할 수 있었다.

쉬운 이해를 위해 1 ~ 10 까지의 카드가 주어졌다고 생각해보자.

실제 적용에서는 이 카드의 번호를 index라고 생각하면 된다.

10

1 2 3 4 5 6 7 8 9 10

그리고 처음에 생각을 잘못했던 부분이 있었는데,

정훈이는 자신의 카드를 분배할 때뿐만 아니라 상대의 카드를 분배할 때도 밑장을 뺄 수 있다.

즉, 모든 카드(1 ~ 10)를 분배할 때 밑장을 뺄 수 있다.

//

res[i] : i번째 카드를 분배할 때, 밑장을 뺄 경우 정훈이의 점수

res[1] = 10 + 2 + 4 + 6 + 8

res[2] = 1 + 2 + 4 + 6 + 8

res[3] = 1 + 10 + 4 + 6 + 8

res[4] = 1 + 3 + 4 + 6 + 8

res[5] = 1 + 3 + 10 + 6 + 8

res[6] = 1 + 3 + 5 + 6 + 8

res[7] = 1 + 3 + 5 + 10 + 8

res[8] = 1 + 3 + 5 + 7 + 8

res[9] = 1 + 3 + 5 + 7 + 10

res[10] = 1 + 3 + 5 + 7 + 9

여기서 우리는 점화식을 뽑아내야 한다.

규칙을 잘 찾아보면 홀수, 짝수 index 카드에서 규칙이 생기는 것을 알 수 있다.

점화식을 뽑아내기 전 먼저 

홀수, 짝수 index 카드의 누적합을 알아야 한다.

sum[][]

   0  1  2  3   4   5

0 [0, 2, 6, 12, 20, 30] : 짝수 index 카드의 누적합 (2+4+6+8+10)

1 [0, 1, 4, 9, 16, 25] : 홀수 index 카드의 누적합 (1+3+5+7+9)

짝수 index

res[2] = sum[1][1] + (sum[0][4] - sum[0][0])

res[4] = sum[1][2] + (sum[0][4] - sum[0][1])

res[6] = sum[1][3] + (sum[0][4] - sum[0][2])

res[8] = sum[1][4] + (sum[0][4] - sum[0][3])

res[10] = sum[1][5] + (sum[0][4] - sum[0][4])

...

=> 짝수 index 점화식 : res[i] = sum[1][(i/2+1)-1] + (sum[0][N/2-1] - [0][(i/2+1)-2])

홀수 index

res[1] = sum[1][0] + (sum[0][4] - sum[0][0]) + 10

res[3] = sum[1][1] + (sum[0][4] - sum[0][1]) + 10

res[5] = sum[1][2] + (sum[0][4] - sum[0][2]) + 10

res[7] = sum[1][3] + (sum[0][4] - sum[0][3]) + 10

...

=> 홀수 index 점화식 : res[i] = sum[1][(i/2+1)-1] + (sum[0][N/2-1] - sum[0][(i/2+1)-1]) + cards[N - 1];

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ20159 {
 
    static int N, cards[];
    
    public static void main(String[] args) throws IOException {
            
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        cards = new int[N];        
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.println(process());
    }
    
    private static int process() {
 
        // 홀수, 짝수의 누적합(0: 짝수, 1: 홀수)
        int[][] sum = new int[2][N/2+1];
        for (int i = 0; i < N; i++) {
            // 짝수일 경우 (zero base)
            if((i + 1) % 2 == 0) sum[0][i/2+1] = sum[0][i/2] + cards[i]; 
            // 홀수일 경우
            else sum[1][i/2+1] = sum[1][i/2] + cards[i]; 
        }
        
        int max = 0;
        int[] res = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int idx = i / 2 + 1;
            // 짝수일 경우
            if(i % 2 == 0) res[i] = sum[1][idx -1] + (sum[0][N/2-1] - sum[0][idx-2]);  
            // 홀수일 경우
            else res[i] = sum[1][idx-1] + (sum[0][N/2-1] - sum[0][idx-1]) + cards[N - 1];
                
            max = Math.max(max, res[i]);
        } 
        
        return max;
    }
 
}