[프로그래머스] 택배 배달과 수거하기(Level 2) greedy

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150369

1. 문제 요약

• 트럭 cap만큼 운반할 수 있음.
• n은 배달할 집의 수
• 트럭은 한번에 cap만큼 배달하고 수거 가능.
• 가장 먼 집 부터 처리하면서 최소 이동거리를 계산한다.

2. 핵심 아이디어

• index를 기반으로 뒤에서 앞으로 내려오면서 계산

3. 풀이 코드

public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        // 가장 먼 거리부터 이동거리를 더하기 위해 greedy방식.
        int remainD = 0, remainP = 0;

        for(int i = n -1; i >= 0; i --){
            remainD += deliveries[i];
            remainP += pickups[i];

            while(remainD > 0 || remainP > 0){
                remainD -= cap;
                remainP -= cap;
                answer += (i + 1) * 2L; //집위치 * 2 = 왕복 이동거리
            }
        }
        return answer;
    }

4. 회고 및 느낀점

• level2에서 처음으로 맞은 greedy문제
• 가장 뒤의 index부터 계산한다를 떠올리는게 관건.