백준 25603 (짱해커 이동식) - java

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

 

문제

짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다.

모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들을 받으려 한다. 하지만, 의뢰를 연속으로 K번 이상 거절하면 이동식의 실력이 거품이었다는 소문이 나기 때문에, 임의의 연속된 K개의 의뢰 중에서 최소 하나 이상의 의뢰는 받아야 한다.

이동식은 가능한 낮은 비용이 드는 의뢰만 받고 싶어 한다. 즉, 수락한 의뢰들의 비용 중 최댓값을 최소화하려 한다. 기업 의뢰 리스트가 주어졌을 때, 위 조건을 만족하면서 의뢰를 수행할 때 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라. 단, 주어진 의뢰의 순서를 임의로 바꿀 수 없다.

 

유형 : 이진 탐색

 

접근 방식

• 특정 값에 대하여 N번의 순차 탐색을 통해 K개를 연속 처리할 수 있는지를 판단한다.
• 값의 범위가 1부터 1000000000이기 때문에 모든 범위를 처리하기에는 무리이기 때문에 이진 탐색을 수행한다.
• K개 구간을 연속으로 처리해가며 완료할 경우 값의 범위를 축약하여 진행한다.

코드

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

public class BOJ_25603_짱해커_이동식 {

    static int n,k;
    static int[] arr;

    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());

        arr = new int[n];

        int min = 1;
        int max = 0;

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());

            max = Math.max(max,arr[i]);
        }

        int result = 0;

        while(min <= max) {
            int mid = (min + max) / 2;

            if(go(mid)) {
                result = mid;
                max = mid - 1;
            }else {
                min = mid + 1;
            }
        }

        System.out.println(result);

        br.close();
    }

    static boolean go(int target) {

        int tmp = 0;

        for(int i = 0 ; i < n ; i++) {
            if(arr[i] <= target) {
                tmp = 0;
                continue;
            }

            tmp++;

            if(tmp >= k) {
                return false;
            }
        }

        return true;
    }
}