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

문제 해석

---

---

문제 풀이

---

결국 어느지점까지 찍고 돌아와야 하니 가장 먼곳을 가장 적게 다녀오는 것이 핵심이겠다고 생각했다.

택배를 배송하고 나면 수거할 공간이 생기니 자명하게 최대 갯수만큼 배송하고 최대갯수만큼 수거하는 것이 좋을 것이다.

 

가장 먼곳에서 최대한 많은 갯수를 동시에 배송하고 수거하는 것이 핵심이라 보고 greedy하게 뒷배열부터 처리해주는 결정을 했다.

또한 횟수가 남는다면 그 다음번에 그 횟수만큼 차감한 후 계산하면 되겠다고 생각하였다.

 

처음 짠 코드는 배송과 수거를 분리하여 고려하고 둘 중에 횟수가 많은 쪽을 정답으로 처리해주었는데

 4, 4, [25, 24, 51, 0], [51, 0, 0, 49] 에서 반례가 생겼다.

 

다시 생각해보니 매 순간마다 더 많이 다녀와야하는 곳이 어디인지 고려하고 결정하는 것이 옳다고 생각되어 코드를 수정하고

정답을 받았다.

---

코   드

---

#include <string>
#include <vector>

using namespace std;

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

---

느낀점: 쉬운 그리디문제라고 생각했는데 고려할 것이 좀 많았다. 백준 택배 문제와 비슷했다.

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

프로그래머스