[백준/JAVA] BOJ 25603 - 짱해커 이동식

슬라이딩 윈도우는 오랜만이라...

👀 문제

25603번: 짱해커 이동식 ✨ 골드 5

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

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

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

예제 입력

5 2
1 3 5 4 2

예제 출력

4

🔑 키포인트

슬라이딩 윈도우

✍️ 코드

📍 k만큼 확인하면서 해당 구간에 수락한 의뢰가 있다면 넘어가고, 없다면 그 구간에서 가장 비용이 적은 의뢰를 수락한다
💡 수락한 의뢰 중에 가장 큰 비용을 찾아 출력해 준다

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

public class BOJ25603_짱해커이동식 {
    static int n, k;
    static int[] cost;

    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());
        cost = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(cal());
    }

    static int cal() {
        boolean[] check = new boolean[n];
        int max_cost = 0;
        int s = 0;

        while (s <= n - k) {
            boolean flag = false;
            int min = Integer.MAX_VALUE;
            int min_idx = 0;
            for (int i = s; i < s + k; i++) {
                if (check[i]) {
                    flag = true;
                    break;
                } else {
                    if (cost[i] < min) {
                        min = cost[i];
                        min_idx = i;
                    }
                }
            }
            if (!flag) {
                check[min_idx] = true;
                max_cost = Math.max(max_cost, min);
            }
            s++;
        }

        return max_cost;
    }
}