문제 링크
문제 요약
그리디 문제에 해당한다.
문제를 이해해보면, 박스를 배달하거나 수거한 부분에 대해서 리스트를 업데이트 해줄 필요는 없다. (처음에 이런 식으로 풀이했다가 시간 초과가 발생했다 .. ^^)
즉, 간단하게 가장 먼 거리에서부터 고려하는 과정으로 문제를 해결해나갈 수 있다!
아래 해설 내용이 헷갈리면 주석 처리해둔 부분을 풀고 돌려보면 감이 잡힐 것이다!
문제 풀이
# cap : 한 번에 들고 갈 수 있는 택배 상자
# n : 집의 개수
def solution(cap, n, deliveries, pickups):
answer = 0
deliver = 0
pickup = 0
for i in range(n-1, -1, -1):
deliver += deliveries[i]
pickup += pickups[i]
#print(f"index : {i}, deliver: {deliver}, pickup: {pickup}")
# 배달 해주거나 / 수거 해주기
while deliver > 0 or pickup > 0:
deliver -=cap
pickup -= cap
#print(deliver, pickup, i)
answer += (i+1)*2
#print(answer)
return answer📌 해결 방법
- deliver와 pickup 변수는 가장 먼 거리에 해당하는 값을 더한 것이다.
- while 문을 활용해서 cap (한 번의 움직임으로 가져가거나 가져올 수 있는 박스의 개수)를 빼주고 다시 for문을 이용해서 더해주는 과정을 진행한다.
- 이 과정에서 while문에 들어온 경우에만 answer가 더해지는데 이때 인덱스에 +1을 해주어야한다.
