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

 

 

1. 백준 25603. 짱해커 이동식 (골5)

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

25603번: 짱해커 이동식

 

풀이

 

CODE

import sys

input = sys.stdin.readline

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

max_cost = 0
idx = 0

while idx + k <= n:
    # 연속된 k개의 의뢰 중 최소비용의 의뢰 택하기
    check = min(costs[idx: idx+k])

    # 택한 의뢰를 기준으로 idx 갱신
    for i in range(k-1, -1, -1):
        if costs[idx + i] == check:
            idx += i + 1
            break

    # 택한 의뢰 비용이 현재의 최대 의뢰비용보다 크면 최대 의뢰비용 갱신
    if check > max_cost:
        max_cost = check


# 동식이가 수락한 의뢰들이 가진 비용 중 가장 높은 비용 출력
print(max_cost)

• 처음에 틀렸는데 질문게시판에 질문이 한 개밖에 없어서 스스로 반례를 찾아서 개선해나간 문제..ㅎㅎㅎ
• 그래서 뿌듯함이 두 배!
• 개선한 내용
  • 처음에 while idx < n: 으로 했는데 고려해야 할 인덱스가 k개 미만이면 뒤의 의뢰는 안받아도 된다.
    그래서 idx + k <= n 으로 변경했다.
  • 택한 의뢰를 기준으로 idx를 갱신하는 과정에서 거꾸로 for문을 쓰지 않으니 시간 초과가 발생했다.
    고려하는 구역 내에 check의 중복이 발생할 때 가장 끝에 있는 check의 index를 택하면 되므로 거꾸로 for문을 통해 다음 index를 갱신했다. 찾으면 바로 break ~.~