[Programmers 150369] 택배 배달과 수거하기

문제

LV2 [Programmers 150369 - 택배 배달과 수거하기]

문제 풀이 방법

문제를 읽고 그리디 문제라는 것을 알 수 있었다. 그리디 문제는 이제는 자신있는(?) 알고리즘이라고 생각했기 때문에 여유로운 마음으로 풀어보았지만 생각보다 쉽지 않았다.. (머리가 굳은 건가..?ㅜㅜ)

트럭 하나로 모든 배달과 수거를 마치고 물류창고로 돌아오는 최소 이동거리를 구하기 위해서는 거리가 먼 집부터 배달과 수거를 완료해야 한다!

1. deliveries와 pickups 배열의 뒤에서 부터 배달하거나 수거해야 될 택배가 있다면 그 때의 거리(인덱스 + 1)를 distance에 저장한다.
2. 배달할 수 있는 택배부터 배달한다.
   1. car라는 변수에 배달할 수 있는 택배 무게를 저장한다.
   2. 만약 현재 집에 택배를 배달할 수 있다면, car 변수에 현재 집의 택배 무게를 누적하여 저장하고 delivery(현재 배달하고 있는 집을 나타내는 인덱스 변수)에 -1을 하여 앞 집을 탐색한다.
   3. 만약, 현재 집에 택배를 일부만 배달할 수 있다면, 현재 집의 택배 무게에서 배달할 수 있는 택배수 만큼만 빼고 반복문을 탈출한다.
3. 수거과정도 2와 같이 반복한다.
4. 1에서 구한 distance의 2배만큼을 answer에 누적하여 더한다.

풀이 코드

Python

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

    delivery = n-1 # 수거 위치를 의미 하는 포인터
    pickup = n-1 # 수거 위치를 의미 하는 포인터
    while delivery >= 0 or pickup >= 0:
        distance = 0
        if delivery >= 0 :
            while delivery >= 0 and deliveries[delivery] == 0: # 옮길 택배가 있을 때까지
                delivery -= 1
            if delivery < 0: distance = 0
            else: distance = delivery+1 # 최대 거리 저장

            car = 0 # 트럭에 있는 택배 무게
            while delivery >= 0 and car < cap: # 현재 집에 택배를 트럭에 실을 수 있다면 싣는다.
                if deliveries[delivery] + car <= cap:
                    car += deliveries[delivery]
                    deliveries[delivery] = 0
                    delivery -= 1
                else:
                    rest = cap - car
                    deliveries[delivery] -= rest
                    break

        if pickup >= 0:
            while pickup >= 0 and pickups[pickup] == 0: # 옮길 택배가 있을 때까지
                pickup -= 1
            if pickup < 0: distance = 0
            else: distance = max(distance, pickup+1) # 최대 거리 저장

            car = 0 # 트럭에 있는 택배 무게
            while pickup >= 0 and car < cap: # 현재 집에 택배를 트럭에 실을 수 있다면 싣는다.
                if pickups[pickup] + car <= cap:
                    car += pickups[pickup]
                    pickups[pickup] = 0
                    pickup -= 1
                else:
                    rest = cap - car
                    pickups[pickup] -= rest
                    break

        answer += distance*2
    return answer

print(solution(2,2, [0,0], [0,0]))