[BOJ] 14465. 소가 길을 건너간 이유 5(누적합).java

#. Problem

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

* 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, K, B의 범위가  (1 ≤ N ≤ 100,000), (1 ≤ B,K ≤ N) 라서

Naive 하게는 해결하기 힘들 것 같았다.

생각한 방법은 누적합이다.

예제로 살펴보면

먼저 K번째 횡단보도까지 망가진 횡단보도의 개수를 count 해주었다.

    X  X        X           X  X

 0  1  2  3  4  5  6  7  8  9  10

[0, 0, 0, 0, 0, 0, 3

다음으로는 K + 1번째 횡단보도부터 누적합을 적용하는데,

현재 횡단보도도 망가진 상태라면 (K번째 누적합)++

K번째 전 횡단보도가 망가져 있다면 (K번째 누적합)--

를 적용해준다. 

7번째 횡단보도는 망가지지 않았고

K번째 전인 1번째 횡단보도는 망가진 상태이므로 

6번째 횡단보도까지의 누적합 - 1 을 저장해준다.

    X  X        X           X  X

 0  1  2  3  4  5  6  7  8  9  10

[0, 0, 0, 0, 0, 0, 3, 2

다음,

8번째 횡단보도는 망가지지 않았고

K번째 전인 2번째 횡단보도는 망가진 상태이므로 

7번째 횡단보도까지의 누적합 - 1 을 저장해준다.

    X  X        X           X  X

 0  1  2  3  4  5  6  7  8  9  10

[0, 0, 0, 0, 0, 0, 3, 2, 1

다음,

9번째 횡단보도는 망가져있고, ++

K번째 전인 3번째 횡단보도는 망가지지 않은 상태이므로

8번째 횡단보도까지의 누적합 + 1 을 저장해준다.

    X  X        X           X  X

 0  1  2  3  4  5  6  7  8  9  10

[0, 0, 0, 0, 0, 0, 3, 2, 1, 2

...

결과는 아래와 같다.

    X  X        X           X  X

 0  1  2  3  4  5  6  7  8  9  10

[0, 0, 0, 0, 0, 0, 3, 2, 1, 2, 3]

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ14465 {
 
    static int N, K, B;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
 
        int[] sum = new int[N + 1];
        boolean[] isBroken = new boolean[N + 1];
        for (int i = 0; i < B; i++) {
            isBroken[Integer.parseInt(br.readLine())] = true;
        }
        
        int cnt = 0;
        // K번째 횡단보도까지 망가진 횡단보도의 개수 count
        for (int i = 1; i <= K; i++) {
            if(isBroken[i]) cnt++;
        }
        sum[K] = cnt;
        int res = cnt;
 
        for (int i = K + 1; i <= N; i++) {
            int tmp = sum[i - 1];
            // 이번 횡단보도도 망가졌다면
            if(isBroken[i]) tmp++;
            // K번째 전에 망가진 횡단보도가 있었다면
            if(isBroken[i - K]) tmp--;
            
            sum[i] = tmp;
            res = Math.min(res, tmp);
        }
        
        System.out.println(res);
    }
 
}