카카오 코딩테스트에서 이 문제를 봤을때 겁부터 먹었던게 생각난다. 이거 DP문제 아닐까 하면서 많이 겁먹었고 끝나고 나서도 아무리 생각해도 이거 어떻게 풀 수 있었지 하면서 멘붕이었는데 이번에 프로그래머스에 문제 올라오고 노트에 천천히 생각하면서 적어보니깐 한시간안에 풀었다. 왜 그때는 이게 어렵다고 느꼈고 푸는거 조차 두려워했는지 이해가 가지않는다...코딩테스트에 조금 더 자신감을 가지고 풀었으면 좋겠다.
이 문제는 출발점에서 택배를 가지고 차가 이동할때 각 집에서 원하는 수의 상자를 배달 시키고 돌아오면서 박스를 수거할 수 있는데 이때 차가 이동하는 최소의 거리를 구해야한다. 첫번째 예시를 읽었을때 살짝 멘붕이 왔던거같다. 어떻게 최소 거리를 얻을 수 있을까? 예시에서는 이상하게 꼭 마지막 집까지 갔다가 돌아오는 시뮬리이션을 보여줬지만 그냥 손으로 처음 집부터 차례대로 가도 괜찮지 않을까 했는데 차이가 없어서 헷갈렸다가 두번째 예시에서 시뮬레이션을 돌려보니깐 확실히 마지막 집의 배달을 먼저 끝내는게 움직이는 거리로 봤을때 더 이득이였다. 왜냐하면은 중복되는 거리가 하나라도 더 줄어들기 떄문.
그렇다면 이 문제는 어떻게 접근해야 할까? 그렇다. 그리디 하게 접근하는게 답이었다. 그리디하게 접근하는 뜻은 트럭이 가진 최대한의 Capacity를 가지고 이동해야 한다는 뜻이다. 이 문제를 풀때는 아래 세가지를 명심하면 된다.
- 끝에서 부터 배달하기 얼마만큼? 최대 Capacity 만큼
- 끝에서 부터 수거하기 얼마만큼? 최대 Capcity 만큼
- Capacity 만큼 이동했는데도 못 끝낸 집이 있다면 그 지점에서부터 다시 시작하기.
이 문제를 해결하기 위해서 투포인터의 개념도 필요하다고 생각했다. 배달을 따라가는 포인터하나, 그리고 수거를 해야하는 포인터하나. 내가 배달이나 수거를 끝낼 수 있고 Capcity가 남는다면은 계속해서 옮겨주는게 맞지만 만약 한 집에서 배달이나 수거를 못끝냈다면 그때 포인터를 끝내줘야한다. 그 후에는 둘의 거리를 비교하고 더 멀리 있는 집의 거리 2를 곱해서 답에다가 더 해주면 된다. 그 다음 While 룹에서는 배달이나 수거를 못끝낸 지점에서 다시 시작하면 된다.
그래서 나는 큰 While 룹 안에다가 For 룹을 두개를 넣었는데, 첫번째 For 룹은 배달용 루프, 두번째 For 룹은 수거용 루프다. 여기서 내가 크게 애를 먹었던 부분은 배달을 할때 아무리 Capcity 만큼 옮겼다 해도 못끝내는 구간이 있을거다. 그렇다면 그 구간을 기준으로 계속해서 배달을 해야하고 옮긴 거리도 기록을 해줘야한다.
만약에 이 문제가 막혔다면은 문제 예시로
Capacity: 2
배달: [0,6]
수거: [0,0]
답 : 12
를 테스트케이스로 넣어보고 테스트하면은 본인의 코드 문제점을 쉽게 알수도 있을거다. 카카오 자체가 원래 코딩테스트가 어렵지만 확실히 로직을 바로 잡는게 중요한거같다... 다음 코딩테스트도 도전해봐야지 화이팅!
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
int start_point = n-1, delivery_point = n-1, pickup_point = n-1, tmp_cap = cap;
bool flag = true;
int compare1 = -1, compare2 = -1;
while(flag){
tmp_cap = cap;
for(int i = delivery_point; i >= 0; i--){
int box = deliveries[i];
if(tmp_cap >= box){
deliveries[i] -= tmp_cap;
tmp_cap -= box;
delivery_point = i;
if(compare1 < 0 && box > 0) compare1 = i;
}
else if(deliveries[i] > 0 && tmp_cap < deliveries[i]){
delivery_point = i;
deliveries[i] -= tmp_cap;
if(compare1 < 0 && box > 0) compare1 = i;
break;
}
}
tmp_cap = cap;
for(int i = pickup_point; i >= 0; i--){
int box = pickups[i];
if(tmp_cap >= box){
pickups[i] -= tmp_cap;
tmp_cap -= box;
pickup_point = i;
if(compare2 < 0 && box > 0) compare2 = i;
}
else if(pickups[i] > 0 && tmp_cap < pickups[i]){
pickup_point = i;
pickups[i] -= tmp_cap;
if(compare2 < 0 && box > 0) compare2 = i;
break;
}
}
answer += compare1 >= compare2 ? (long long)((compare1+1) * 2) : (long long)((compare2+1) * 2);
if(delivery_point == 0 && pickup_point == 0 && deliveries[0] <= 0 && pickups[0] <= 0) flag = false;
compare1 = -1, compare2 = -1;
}
return answer;
}
