[BOJ] 14465 소가 길을 건너간 이유 5 - JAVA

1. 문제

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

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

---

2. 풀이

1.  N+1길이의 배열을 만든다. 신호등이 고장났는지 체크하는 배열이다. 고장나면 true, 정상이라면 false가 저장된다.

2.  B만큼 고장난 신호등을 입력받아서 light배열 값을 바꿔준다.

3.  초기값을 위해서 1부터 K까지 고장난 신호등이 몇갠지 센다.(tmp저장) 그 값을 min에 먼저 저장한다.

4.  K+1부터 N까지 하나씩 옮겨가면서,

4-1.  i-K번째(맨 앞. 더이상 포함하지 않는 위치)가 고장났다면 tmp-1한다. 

4-2.  i번째(새로 추가할 위치)가 고장났다면 tmp+1한다.

4-3.  변경된 tmp를 min값과 비교해 더 작은 값을 min에 저장한다.

5.  min을 출력한다.

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

public class BOJ_14465_소가길을건너간이유5 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());
      int B = Integer.parseInt(st.nextToken());
      boolean[] light = new boolean[N+1];
      for(int i=0;i<B;i++) light[Integer.parseInt(in.readLine())] = true;

      int tmp = 0;
      for(int i=1;i<=K;i++) if(light[i]) tmp++;

      int min = tmp;
      for(int i=K+1;i<=N;i++){
         if(light[i-K]) tmp--;
         if(light[i]) tmp++;

         min = Math.min(min,tmp);
      }

      System.out.println(min);
   }
}

---

3. 결과