[백준/파이썬] 25063번 짱해커 이동식 KAUPC 항공대 알고리즘 대회 문제

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

25603번: 짱해커 이동식

 

문제 해석

 

N개의 의뢰가 주어진다.

두번째 줄에 N개의 의뢰의 비용이 주어진다.

의뢰의 순서는 변경 불가능하다.

의뢰는 항상 K개 중 하나는 선택해야 한다.

최대한 난이도가 낮은 의뢰를 선택하면서, 가장 높은 비용의 최솟값을 구하면 되는 문제이다.

---

코드

 

from collections import deque
input = __import__('sys').stdin.readline

n, k = map(int, input().split())
cost = list(map(int, input().split()))

def solve():
    s = 0
    minCost = cost[0]
    ans = cost[0]
    # 첫 의뢰 수락
    for i in range(s, s + k):
        if cost[i] <= minCost:
            minIdx = i
            minCost = cost[i]
            ans = minCost
    s = minIdx + 1
    
    while s + k <= n:
        q = deque()
        i = s
        minWindow = 0
        # 윈도우 만들기
        for j in range(i, n):
            # 슬라이딩 윈도우가 k개가 되기 전에 최소 비용중 최댓값(구하려는 답)보다 작은 값이 발견한 경우
            if cost[j] <= ans:
                # 슬라이딩 윈도우를 현재 idx의 다음부터 다시 탐색
                s = j + 1
                break
            
            else:
                # 큐에 값을 현재 넣음
                q.append(cost[j])
                # 슬라이딩 윈도우 중에 가장 작은 값, 해당 인덱스 초기 세팅
                if minWindow == 0: 
                    minWindow = cost[j]
                    minWindowIdx = j
                else:
                    # 윈도우 내에 최소 값, 인덱스 갱신
                    if cost[j] <= minWindow:
                        minWindow = cost[j]
                        minWindowIdx = j
                
                # 만약 윈도우가 다 찼다면 답 갱신
                if len(q) >= k:
                    s = minWindowIdx + 1
                    ans = minWindow
                    break
    return ans
print(solve())

---

문제 풀이

 

슬라이딩 윈도우 기법을 생각하며 풀었다.

K 크기의 윈도우 중에서 하나의 의뢰는 반드시 선택해야하며, 선택한 의뢰중 가장 최대값의 비용을 ans에 항상 저장한다.

저장된 ans의 비용보다 낮은 비용의 의뢰는 계속 선택해주면서 윈도우를 슬라이딩 해준다.

K 크기의 윈도우에 ans보다 낮은 비용의 의뢰가 없다면 해당 윈도우에서 가장 최소값이 되는 의뢰를 선택하고 ans값을 갱신해준다.

이를 반복하여 윈도우의 끝이 마지막 의뢰에 도달하게 된다면 종료한다!

 

s = 0
minCost = cost[0]
ans = cost[0]
# 첫 의뢰 수락
for i in range(s, s + k):
    if cost[i] <= minCost:
        minIdx = i
        minCost = cost[i]
        ans = minCost
s = minIdx + 1

초기에 윈도우 범위를 (s, s+k)로 잡아 주었다. 해당 값들을 탐색하면서 최소 비용의 의뢰를 찾고, 해당 값을 ans값으로 갱신해주었다.

이후 그 의뢰는 수행했으므로 그 의뢰의 인덱스 값 + 1 의 값을 s 값으로 지정해주었다.

while s + k <= n:
    q = deque()
    i = s
    minWindow = 0
    # 윈도우 만들기
    for j in range(i, n):
        # 슬라이딩 윈도우가 k개가 되기 전에 최소 비용중 최댓값(구하려는 답)보다 작은 값이 발견한 경우
        if cost[j] <= ans:
            # 슬라이딩 윈도우를 현재 idx의 다음부터 다시 탐색
            s = j + 1
            break

        else:
            # 큐에 값을 현재 넣음
            q.append(cost[j])
            # 슬라이딩 윈도우 중에 가장 작은 값, 해당 인덱스 초기 세팅
            if minWindow == 0: 
                minWindow = cost[j]
                minWindowIdx = j
            else:
                # 윈도우 내에 최소 값, 인덱스 갱신
                if cost[j] <= minWindow:
                    minWindow = cost[j]
                    minWindowIdx = j

            # 만약 윈도우가 다 찼다면 답 갱신
            if len(q) >= k:
                s = minWindowIdx + 1
                ans = minWindow
                break

슬라이딩 윈도우를 통해 최소값을 갱신해주면 된다.

q가 윈도우이다. q에 (s, s+k)만큼 값을 지속적으로 넣어주며 윈도우 내의 최소값을 갱신한다.

ans값보다 작은 값이 들어가면 해당 의뢰는 수행한다.

즉 큐를 초기화하고 해당 의뢰 인덱스 + 1 부터 다시 탐색한다.

 

큐에 값을 넣다가 윈도우크기가 꽉 차게 된다면 윈도우 내 최소값을 선택해 해당 의뢰를 수행한다.

(ans갱신, 인덱스 갱신)

이를 반복하면 답을 구할 수 있다!

엣지케이스를 잘 확인하자..