[그리디] 무지의 먹방 라이브

1. 문제

무지의 카카오 TV 방송 !

1. 1번 음식부터 순서대로 먹기 시작함

2. 마지막 번호의 음식을 먹고나면 다시 1번 음식을 먹음

3. 1초에 한 음식만 먹고, 다음 음식은 남아있는 음식 중 가장 가까운 번호의 음식

4. 다음 번호의 음식이 오는데 걸리는 시간은 없음

 

K초가 지났다. 몇 번 음식을 먹어야 하는가?

2. 입력

# SET - 1
food_times=[3, 1, 2]
K = 5

# SET - 2
food_times = [4, 2, 3, 6, 7, 1, 5, 8]
K = 27

# SET - 3
food_times = [4, 2, 3, 6, 7, 1, 5, 8]
K = 16

3. 출력

# SET - 1
result = 1

# SET - 2
result = 5

# SET - 3
result = 3

4. 풀이

한 음식을 다 먹을때까지 걸리는 시간 = 남아있는 음식의 수 * (현재 음식을 먹는데 걸리는 시간 - 이전까지 먹은 시간)

 

우선순위 큐를 사용해 먹는데 가장 짧게 걸리는 음식부터 순서대로 비교한다.

K = 현재까지 음식을 먹고 남은시간

 

다음 음식을 먹는데 걸리는 시간을 계산하기위해,

previous에 이전에 다 먹은 음식 시간을 저장

그러면 현재 먹는 음식 - previous는 앞으로 먹는데 걸리는 시간의 기준이된다.

 

while K >= (q[0][0] - previous) * length

만약 while문 조건이 False일 때, 

= K가 다음 음식을 다 먹는데 걸리는 시간보다 작으면, K를 length로 나눈 나머지가

(음식 번호 순서대로 정렬했을 때) 남아있는 음식에서 먹어야될 음식의 번호가 된다.

5. 코드

import heapq

def solution(food_times, K):
    if sum(food_times) <= K:
        return -1
    
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i+1))

    previous = 0
    length = len(q)
    while K >= (q[0][0] - previous) * length:
        now, idx = heapq.heappop(q)
        K -= (now-previous)*length
        previous = now
        length -= 1

    q = sorted(q, key=lambda i : i[1])
    return q[K%length][1]