[백준 P14465] 소가 길을 건너간 이유 5 Java

P14465  소가 길을 건너간 이유5

14465번: 소가 길을 건너간 이유 5

문제

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력값

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

10 6 5
2
10
1
5
9

출력값

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

1

알고리즘

존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다.

현재 입력 값으로 주어지는 신호등들이 고장난 신호등의 인덱스이다.

K개의 길이 동안 고장난 신호등이 없어야 한다.

따라서 고장난 신호등의 개수를 누적하면서 배열에 저장하고, 시작점을 이동하면서 시작점 ~ 시작점 + K 의 구간에 가장 적은 수의 고장난 신호등의 수를 뽑아내면 된다.

코드

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

public class Main {

    static int N, K, B;
    static int[] light;
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        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());

        light = new int[N + 1];

        for (int i = 0; i < B; i++) {
            light[Integer.parseInt(br.readLine())] = 1;
        }

        for (int i = 1; i <= N; i++) {
            light[i] += light[i - 1];
        }

        int idx = K;
        while (idx <= N) {
            answer = Math.min(answer, light[idx] - light[idx - K]);
            idx++;
        }

        System.out.println(answer);
    }
}