알고리즘 문제 풀이(프로그래머스 - 택배 배달과 수거하기)

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

• 사용 언어 : javascript

• 해결 날짜 : 2023-05-15

• 해결 방법 :

  • dp를 활용해 문제 해결
    • 먼 거리부터 배달, 수거하는 것이 최소 이동 거리이므로 마지막 인덱스부터 탐색
    • 현재 인덱스의 dp값을 다음 인덱스(i + 1)에서 각각 deliveries[i], pickups[i] 뺀 값으로 업데이트
      • 뺐을 때 둘 중 하나라도 0 미만인 경우(현재 인덱스까지 1번 이상 도달해야 배달과 수거를 완료할 수 있는 경우)
        • 완료할 수 있을 때 까지 dp cap만큼 증가하여 업데이트

• 회고 :

  • x

• 코드

  function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    const dp = Array.from({ length: n + 1 }, () => [0, 0]);
  
    for (let i = n - 1; i >= 0; i--) {
      dp[i][0] = dp[i + 1][0] - deliveries[i];
      dp[i][1] = dp[i + 1][1] - pickups[i];
  
      if (dp[i][0] < 0 || dp[i][1] < 0) {
        const distance = (i + 1) * 2;
        let repeat = 0;
  
        while (dp[i][0] < 0 || dp[i][1] < 0) {
          dp[i][0] += cap;
          dp[i][1] += cap;
          repeat += 1;
        }
  
        answer += distance * repeat;
      }
    }
  
    return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges