728x90
반응형
문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/150369
풀이:
def solution(cap, n, deliveries, pickups):
answer = 0
while deliveries or pickups:
while deliveries and deliveries[-1] == 0:
del deliveries[-1]
while pickups and pickups[-1] == 0:
del pickups[-1]
answer += 2 *(max(len(deliveries),len(pickups)))
x = cap
for i in reversed(range(len(deliveries))):
if x < deliveries[i]: # 더 많이 가지고 있음
deliveries[i] -= x
break
else:
x -= deliveries[i]
deliveries[i] = 0
y = cap
for i in reversed(range(len(pickups))):
if y < pickups[i]: # 더 많이 가지고 있음
pickups[i] -= y
break
else:
y -= pickups[i]
pickups[i] = 0
return answer
그리디 알고리즘이다, 같은 인덱스에서 둘 중에 큰값 만큼은 무조건 가야 최선의 방법이다.
반응형
댓글