이 문제는 그래도 다른 문제들에 비해 읽기 쉬웠다
핵심만 남겨놓고 보면, 택배든 수거든 가장먼것부터 가져오고, cap이 남아있다면 겸사겸사 가장 먼것 중에서 남은 칸을 채워 쓰는 방법이 가장 효율적이다.
이렇게 생각해놓고 보면 코드를 정말 논리 그대로 반복문과 리스트로 풀면 좋겠지만 뭔가 그럼에도 사용할 수 있는 방법은 없을까? 하다가 bfs로 풀어볼까? 싶어서 바로 짜보았다.
from collections import deque
# 가장 먼것부터 배달
# 가장 먼것부터 회수, 칸이 남는 한에 회수
def solution(cap, n, deliveries, pickups):
ans = 0
d_dq = deque()
p_dq = deque()
for i in range(n):
if deliveries[i] != 0:
d_dq.append(i)
if pickups[i] != 0:
p_dq.append(i)
while d_dq and p_dq:
d = d_dq.popleft()
p = p_dq.popleft()
ans += (max(d,p) + 1) * 2
# 남은 배달 마치기
if d_dq:
cur = cap
while d_dq:
tmp = d_dq.popleft()
cur = max(cur, tmp) #여기서 부터 꼬임
ans += cur
if p_dq:
cur = cap
while p_dq:
tmp = p_dq.popleft()
cur = max(cur, tmp)
ans += cur
return ans
from collections import deque
# 가장 먼것부터 배달
# 가장 먼것부터 회수, 칸이 남는 한에 회수
def solution(cap, n, deliveries, pickups):
ans = 0
d = 0
p = 0
deliveries.reverse()
pickups.reverse()
for i in range(n):
d += deliveries[i]
p += pickups[i]
while d > 0 or p > 0:
# 둘중 하나가 음수가 된다고 break하지 않아도 된다
d -= cap
p -= cap
ans += (n - i) * 2
return ans