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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 가장 짧은 이동거리를 구하는 문제다.

 

여기서 중요한 점은 어차피 배달을 하거나 수거를 할 때 가장 먼 집을 들리게 된다는 점이다.

 

이때, 최소한의 거리를 이동하기 위해서는 가장 먼 거리에 있는 택배와 수거해야하는 택배를 먼저 수거해야 다시 먼 거리를 이동하지 않는다는 점이다.

 

아래 그림을 참고하면 이해가 쉽다.

 

어차피 먼 거리에 있는 택배를 가져오기 위해서 들려야 하므로 이동했을 때 먼 거리에 있는 택배를 먼저 가져오는게 무조건 최소 거리를 이동하는 방법이 된다.

 

그리고 이동할 때 가장 먼 거리에 있는 택배부터 가져오거나 수거한다.

그러므로 이 때 이동하는 거리는 수거하는 택배와 배달하는 택배 중 더 멀리 있는 거리만큼 이동하게 된다.

 

 

문제를 풀 때 Index를 이용해 다음에 어떤 거리에 있는 택배를 가져올지 저장하고, 가장 먼 거리에 있는 택배들을 배달하고 수거하도록 코드를 구현했다.

 

​

[아이디어 정리]

1. 가장 먼 거리에 있는 택배와 가장 먼 거리에 있는 수거하는 택배를 먼저 가져온다.
2. 한번에 이동하는 거리는 배달하는 택배와 수거하는 택배 중 더 멀리있는 거리만큼 이동한다.
3. 최종적으로 이동한 거리를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    int dCap=cap,pCap=cap,dIdx=-1,pIdx=-1; //택배, 거리
    long long answer=0;
    for (int i=n-1; i>=0; i--)
    {
        if (deliveries[i]>0){
            dIdx=i;
            break;
        }
    }
    for (int i=n-1; i>=0; i--)
    {
        if (pickups[i]>0){
            pIdx=i;
            break;
        }
    }
    while(dIdx>=0||pIdx>=0)
    {
        // 처음이동 거리 
        answer+=2*(1+max(dIdx,pIdx));
        dCap=cap;
        pCap=cap;
        while(dIdx>=0)
        {
            if (deliveries[dIdx]>dCap)
            {
                deliveries[dIdx]-=dCap;
                break;
            }
            else
            {
                dCap-=deliveries[dIdx];
                deliveries[dIdx]=0;
                dIdx--;
            }
        }
        while(pIdx>=0)
        {
            if (pickups[pIdx]-pCap>0)
            {
                pickups[pIdx]-=pCap;
                break;
            }
            else
            {
                pCap-=pickups[pIdx];
                pickups[pIdx]=0;
                pIdx--;
            }
        }
    }
    return answer;
}

 

---

처음에 문제를 풀고 통과가 안돼서 내가 모르는 반례가 있나 고민을 했다...

그런데 아무리 생각해도 반례가 없는 것 같아서 다른 사람들의 질문을 참고했더니 long long형태의 반환값을 int로 선언해 사용하고 있었다...

 

아오 오랜만에 또 당했다;;

프로그래머스