https://school.programmers.co.kr/learn/courses/30/lessons/150369

일렬로 있는 집에 택배 배달하고 수거박스 회수해야하는데 효율적으로 했을 때의 거리 찾는 문제이다.

Python

1차 실패

def solution(cap, n, deliveries, pickups):
    answer = 0

    d = []
    p = []
    for i in range(n):
        if deliveries[i]:
            d.append((i+1, deliveries[i]))
        
        if pickups[i]:
            p.append((i+1, pickups[i]))
    
    while d and p:
        next = max(d[-1][0], p[-1][0])
        
        answer += next * 2
        
        pos = cap
        
        while pos > 0 and d:
            idx, now = d.pop()
            if now - pos > 0:
                d.append((idx, now - pos))
            pos -= now
        
        pos = cap
        while pos > 0 and p:
            idx, now = p.pop()
            if now - pos > 0:
                p.append((idx, now - pos))
            pos -= now
    
    return answer

문제에서 예시 풀어준 방법대로 접근했다. 맨 마지막 집까지 간다는 가정으로 택배 배달해주고 오는길에 먼 집부터 박스 회수하고 그렇게 접근했는데 틀렸다.
DP를 써야하나보다.

시도 2

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    # DP인데 그때 도서관이랑 비슷한 알고리즘인 것 같은데 
    # 점화식 어떻게 세우지?
    # dp[n] = min(list(dp[n-k] for k in range(1, cap))) => dp[n-1] ... dp[n-cap + 1] + 1
    # 또 각 집마다 cap보다 더 많은 상자 혹은 택배가 있을 수도 있네
    # 먼집부터 먼저 처리하는게 나은가보다
    # 먼집 가서 택배주고 가져올거 있으면 가져오고
    
    # dp[n] = min(list())
    # 가까운데 부터 배달가고, 
    
    # 가야하는 집만 빼기
    d = []
    p = []
    for i in range(n):
        if deliveries[i]:
            d.append((i+1, deliveries[i]))
        
        if pickups[i]:
            p.append((i+1, pickups[i]))
    
    while d or p:
        next = max(d[-1][0] if d else 0, p[-1][0] if p else 0)
        
        answer += next * 2
        
        pos = cap
        
        while pos > 0 and d:
            idx, now = d.pop()
            if now - pos > 0:
                d.append((idx, now - pos))
            pos -= now
        
        pos = cap
        while pos > 0 and p:
            idx, now = p.pop()
            if now - pos > 0:
                p.append((idx, now - pos))
            pos -= now
    
    return answer

DP는 안 써도 됐다. 그냥 조건이 잘못됐을 뿐이었다.

1, 5, [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]인 경우에 배달에 대해서는 작동해야하는데 최초 코드에서
while d and p: 로 조건을 줘서 아예 작동을 안 했던 거였다. 그래서 조건을 변경해주니까 작동했다.