[카카오] 택배 배달과 수거하기 (Java)

🍇 문제

2023 KAKAO BLIND RECRUITMENT Lv.2 택배 배달과 수거하기
https://school.programmers.co.kr/learn/courses/30/lessons/150369

n개의 집에 택배를 배달 및 수거해야 한다.
트럭은 최대 cap 만큼의 택배를 실을 수 있다.
트럭이 i번째 집까지 가는데 i 만큼의 거리가 걸린다. (1 <= i <= n)
트럭이 모든 택배를 배달 및 수거하는데 걸리는 최소의 거리를 구하라.

• int cap : 트럭에 실을 수 있는 최대 택배 개수
• int n : 배달할 집의 개수
• int[] deliveries : 각 집에 배달할 재활용 택배 상자의 개수를 담은 배열
• int[] pickups : 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 배열

🍇 풀이

n번째부터 1번째 집까지 반복문을 돌면서 필요한 트럭의 최소 이동 거리를 구한다.

DP인 줄 알고 겁부터 먹었는데, 막상 풀이를 찾아보니 간단한 문제였다. 마지막 집에서 모든 배달 및 수거를 완료하고, 돌아오면서 추가적인 수거를 할 수도 있으니 반복문을 거꾸로 돌아야 했다. 가끔 가다가 이렇게 뒤에서부터 업데이트 해줘야하는 문제가 있는데, 문제를 잘 읽고 거꾸로 도는 반복문도 한 후보로 꼭 생각해두어야겠다.

🍇 전체 코드

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliever = 0; // 트럭에 실려 있는 배달 상자 수
        int pickup = 0; // 트럭에 실려 있는 수거 상자 수
        
        for (int i = n - 1; i >= 0; i--) {
            int cnt = 0;
            
            if (deliveries[i] > 0 || pickups[i] > 0) {
                while (deliever < deliveries[i] || pickup < pickups[i]) { // 배달 및 수거 완료까지 하나라도 남아있으면 들린다.
                    cnt++;
                    
                    deliever += cap;
                    pickup += cap;
                }
                
                deliever -= deliveries[i]; // 남는 자리
                pickup -= pickups[i]; // 남는 자리
                
                answer += (i + 1) * cnt * 2; // 거리 * 횟수 * 왕복
            }
        }
        
        return answer;
    }
}

🍇 Comment

거꾸로도 생각해보자.