택배 배달과 수거하기

프로그래머스 택배 배달과 수거하기 풀이

문제설명

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

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.

배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)

트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

분석

문제는 그리디 문제같다. 최소값을 구하는 문제이다. 처음에는 그리디하게 완전탐색을 생각했다. 가장 밖에 있는 물건부터 가져오면, 그게 최적의 해라 생각했다. 가장 밖에 있는 물건을 가져오면, 가져오는 동안 나머지 집에 있는 물건을 가져올 수 있다. 그렇기에 최대(Cap)수량만큼 배달 및 수거가 가능하다. 모든 물건이 배달될 때까지 배달을 시도하고, 시도할때마다 가장 밖에 있는 물건부터 차근차근 없애나갔다.

나는 $O(N^2)$으로 해결했다.

while(남은 배달 박스 + 남은 수거 박스){
		1. 수거 박스와 배달 박스 중 더 밖에 있는 것 선택
		2. 밖부터 안까지 최대한 많은 물건을 배달 및 수거
		3. ans += (멀리간 위치)*2;
}

문제를 해결하고, 다른 사람의 풀이를 봤는데 O(N)으로 해결했다.

남은 배달박스와 수거박스를 역으로 순회하면서, 남은 수량을 변수에 저장해놓는다. 남은 수량 - 현재 수량을 했을 때, 이 값이 0보다 작을때만 이 위치까지 배달이 필요하므로 배달 및 수거하고, 남은 수량을 업데이트 한다. 남은 수량은 배달한 횟수 * CAP - (배달, 수거가 필요한 값)으로 업데이트하면된다.

소스코드

#include <bits/stdc++.h>
using namespace std;
int box = 0;
int empty_box = 0;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    
    int end = deliveries.size();
    int d_cnt = 0, p_cnt = 0; // 각 남은 수량
    
    long long ans = 0;
    for(int i = end - 1; i>=0; i--){
        int deliver = deliveries[i];
        int pickup = pickups[i];
        d_cnt -= deliver; p_cnt -= pickup;
        if(d_cnt >= 0 && p_cnt >= 0) continue;
        int cnt = max((-d_cnt -1)/cap + 1, (-p_cnt -1)/cap + 1);
        d_cnt += cnt*cap;
        p_cnt += cnt*cap;
        ans += cnt * (i+1);
    }
    
    return (long long)ans * 2;
}

배운점

문제를 최대한 단순하게 생각하자. 프로그래머스에서는 비교적 시간제한을 많이 안두는 데, 나는 최적의 코드만 찾으려한다. 백준 문제풀이를 주로하다보니, 시간제한에 맞춰 문제를 푸는 것에 습관이 되서 그렇다.