[프로그래머스][C++][150369] 택배 배달과 수거하기

[문제 출처]

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

1. 문제

설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

 

배달 및 수거할 재활용 택배 상자 개수

배달 및 수거 과정

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

입출력 예

2. 설명

 문제를 어떻게 풀어야 하는지 전혀 감도 안왔으나 https://school.programmers.co.kr/questions/43364 이분의 설명을 보고 이렇게 풀수도 있구나 하는 생각을 가지게되었습니다.

 

 

  d는 배달하는 상자의 개수를 담는변수이고, p는 픽업하는 상자의 개수를 담는 변수입니다. 각자 그 위치의 상자개수만큼 빼줍니다.

 

 그 후 두개 모두 0이상이어야 배달과 회수를 처리할수있으므로 cap만큼 더해줍니다. cnt또한 더해줍니다. 이렇게 해주는 이유는 만약 cap= 2, d=-5,  p=-2라면 d=1, p=4, cnt=3이되게 됩니다. 즉 3번 왕복했을때 옮길수있는 총 개수는 6개인데 거기서 원래의 값을 뺀것입니다. 남은숫자는 다음번 값을 처리할때도 쓰이게 됩니다. 
 

 이제 거리를 더해줄것인데 원소에 접근하기위해 i-1을 했었으니 다시 더하고, 왕복이니까 2를 곱하고, cnt번만큼 왕복했으니 cnt를 곱해줍니다. answer+=(i+1)*2*cnt; 처리해주었으니 다시 cnt를 초기화시켜줍니다.

 

 

문제는 굉장히 복잡했지만 막상 푸는방법은 굉장히 간단했습니다. 혼자서도 생각할수있게 연습해야겠습니다.

 

3. 코드

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int d=0, p=0, cnt=0;
    
    for(int i=n-1; i>=0; i--){
        d-=deliveries[i];
        p-=pickups[i];
        
        while(1){
            if(d>=0 && p>=0)
                break;
            d+=cap;
            p+=cap;
            cnt++;
        }
        answer+=(i+1)*2*cnt;
        cnt=0;
    }
    return answer;
}