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

-문제

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

프로그래머스

코드

function solution(cap, n, deliveries, pickups) {
  let answer = 0;

  // d는 배달하는 택배 용량, p는 픽업하는 택배 용랸
  let d = 0,
    p = 0;

  for (let i = n - 1; i >= 0; i--) {
    // cnt는 그 지점까지 왕복을 몇 번 했는지
    let cnt = 0;

    // 만약 d나 p가 음수이면 왕복을 한 번 더 해야한다.
    d -= deliveries[i];
    p -= pickups[i];

    while (d < 0 || p < 0) {
      // d나 p가 음수이면 왕복이 더 필요하다.
      // 아래처럼 cap를 더하면 왕복을 한 번 더 한거다.
      d += cap;
      p += cap;

      // 왕복을 더 했으니까 cnt를 올려줘야한다.
      cnt++;
    }

    answer += (i + 1) * 2 * cnt;
  }

  return answer;
}

문제 풀이

이 문제를 풀기 전에 이해해야 하는 개념이 있다. 택배를 배송하는 것과 수거하는 것은 독립적으로 봐도 된다. 왜냐하면 택배를 마지막으로 배달하는 집에 도착하는 순간 트럭에 실을 수 있는 용량은 다시 cap만큼 늘어나기 때문이다. 그렇기에 배달과 수거는 맨 마지막 집을 기준으로 생각하는 것이 좋다.

 

-변수 d, p

  // d는 배달하는 택배 용량, p는 픽업하는 택배 용랸
  let d = 0,
    p = 0;

변수 d는 배달하는 택배 용량이고, p는 픽업하는 택배 용량이다.

 

-for문

마지막 집부터 생각해야 하므로 반복문을 역순으로 돌려줘야 한다.

  for (let i = n - 1; i >= 0; i--) {
    // cnt는 그 지점까지 왕복을 몇 번 했는지
    let cnt = 0;

    // 만약 d나 p가 음수이면 왕복을 한 번 더 해야한다.
    d -= deliveries[i];
    p -= pickups[i];

    while (d < 0 || p < 0) {
      // d나 p가 음수이면 왕복이 더 필요하다.
      // 아래처럼 cap를 더하면 왕복을 한 번 더 한거다.
      d += cap;
      p += cap;

      // 왕복을 더 했으니까 cnt를 올려줘야한다.
      cnt++;
    }

    answer += (i + 1) * 2 * cnt;
  }

cnt는 그 지점까지 왕복을 몇 번 했는지 저장하는 변수이다. 

각 지점에 갈 때마다 d와 p에 각각 배달 택배와 수거 택배를 빼준다. 그 지점에서 d와 p가 음수라는 의미는 트럭이 왕복을 한 번 더 해야 한다. 그렇기에 왕복을 위해 d와 p에 cap을 더해주고 cnt를 1 올려줘야 한다.

answer에는 그 지점의 위치에 왕복이라서 곱하기 2와 왕복 횟수인 cnt를 곱해줘야 한다.