BOJ : 14465

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

연속하는 K개의 신호등이 있을때 최소 신호등 수리 횟수를 구하는 문제이다.

 

1트) for문으로 인덱스를 통해 구간 반복문으로 풀려고 했다. 95퍼에서 틀림.

2트) 신호등 인덱스별로 고장난 신호등 개수를 저장해놓고 최솟값을 계산한다. 정답

 

3. 코드

 

package week8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q14465_boj {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int arr[] = new int[N+1];

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

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

        int result = 0;

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

        int index = K;
        while(index <= N){
            result = Math.max(result, arr[index] - arr[index-K]);
            index++;
        }

        System.out.println(K-result);
    }
}

 

4. 시간복잡도

 

O(N)

 

5. 결과