문제

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

---

입력

• 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap
• 배달할 집의 개수를 나타내는 정수 n
• 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries
• 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups

---

출력

• 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리

---

풀이

제한조건

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000

접근방법

Greedy

특별한 알고리즘을 요구하지 않는 문제이다. 단순 구현이지만 그리디하게 접근하면 된다.
그리디인 이유는 가장 먼 위치의 집부터 우선 방문해야 한다.

가장 멀리 갔을 때 최대한의 수로 이동해야 가장 먼 위치를 최소한의 왕복으로 다녀올 수 있다.
하지만, 근처부터 배달과 수거를 시작한다면, 먼 위치로 갈 수록 비효율적인 배달을 해야한다.

따라서 맨 마지막에 위치하는 곳부터 배달과 수거를 진행하면 된다.

번외
최대 또는 최소값을 구하기 위해서 Math.max 또는 min 함수를 주로 이용하는데,
해당 함수는 함수 호출 비용이 너무 크다.

알고리즘 시간 최적화를 위해서라면 삼항연산자 또는 if문을 사용해주자.

---

코드

class Solution {
	public long solution(int cap, int n, int[] deliveries, int[] pickups) {
		long answer = 0;
        n -= 1;
		while (n >= 0) {
			if (deliveries[n] + pickups[n] == 0) {
				--n;
				continue;
			}
			answer += (n + 1) * 2;

			moveTruck(n, cap, deliveries);
			moveTruck(n, cap, pickups);
		}

		return answer;
	}

	private void moveTruck(int n, int remain, int[] arr) {
		while (n >= 0) {
            int min = remain > arr[n] ? arr[n] : remain;
			//int min = Math.min(remain, arr[n]);
			remain -= min;
			arr[n] -= min;
			if(remain == 0)
				break;
			--n;
		}
	}
}