[Python/BOJ] 25603. 짱해커 이동식

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

25603번: 짱해커 이동식

문제

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

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

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

입력

첫 번째 줄에 정수 N, K가 주어진다. (1≤K<N≤100000)

두 번째 줄부터 N개의 기업 의뢰의 비용이 주어진다. 비용은 1 이상 10^9 이하의 정수이다.

출력

이동식이 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라.

풀이

Code

import sys
input = sys.stdin.readline

# 1. 주어진 범위 내 최솟값 인덱스 반환 함수 정의
def return_idx(idx) :
    cost = float('inf')
    # 1-1.
    for i in range(idx+k, idx, -1) :
        # 더 작은 비용 값을 가지는 경우
        if costs[i] < cost :
            # 인덱스, 비용 업데이트
            new_idx = i
            cost = costs[i]
    # 1-2. 업데이트 된 인덱스와 비용 반환
    return new_idx, cost
def solution(n, k, costs) :
    # 2. 초기 범위 내 최솟값을 갖는 인덱스와 비용 설정 
    idx = costs[:k].index(min(costs[:k]))
    answer = costs[idx]
    # 3.
    while idx + k < n :
        # 3-1. 최솟값 인덱스 반환 함수 실행
        idx, cost = return_idx(idx)
        # 3-2. 최댓값 업데이트
        answer = max(answer, cost)
    # 4. 결과 출력
    print(answer)
if __name__ == '__main__' :
    n, k = map(int, input().split())
    costs = list(map(int, input().split()))
    solution(n, k, costs)