쌓고 쌓다
[프로그래머스] 택배 배달과 수거하기 C++ 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/150369#qna
풀이 방법
최소 이동 거리로 배송과 픽업을 모두 완료하려면
계속 가장 먼 거리의 집을 먼저 방문하며 배송과 픽업을하면 된다.
가장 먼 거리의 집(픽업 또는 배송이 필요한 집)을 가는길에
배송이 필요한 가장 먼 집들을 배송을 진행하고
픽업이 필요한 가장 먼 집들을 픽업을 진행하면 된다.
전체 코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
// 현재 방문해야할 집 (젤 끝 집부터 방문)
int dIdx = n-1;
int pIdx = n-1;
// 배송과 픽업 인덱스가 둘다 -1이 될때까지 방문
while (dIdx >= 0 || pIdx >= 0) {
// 배송이 필요한 가장 먼 집 인덱스
while (dIdx>=0 && deliveries[dIdx] == 0) {
dIdx--;
}
// 픽업이 필요한 가장 먼 집 인덱스
while (pIdx>=0 && pickups[pIdx] == 0) {
pIdx--;
}
// 배송과 픽업중 가장 먼 거리를 통해 배달과 픽업 모두 해결이 가능함.
// 배달이 더 먼 거리라면 배달하고 창고로 가는길에 픽업하면 됨
// 픽업이 더 먼 거리라면 픽업하러 가는길에 배달하면 됨
// 즉 각각 수행한다고 생각하는게 편함.
// 할일이 있는 최대 먼 거리를 통해 왕복 거리를 계산
int distance = max(dIdx, pIdx) + 1;
answer += distance*2;
// 배송 가능한 용량
int deliverCap = cap;
while(deliverCap>0 && dIdx>=0) { // 배송 용량이 남아 있고, 배송 집이 남아 있다면
if(deliveries[dIdx] <= deliverCap) { // 배송할 상자 <= 배송 가능 용량
deliverCap -= deliveries[dIdx]; // 배송할 상자만큼 용량 줄임
deliveries[dIdx] = 0; // 배송 요구만큼 모두 배송
} else { // 배송할 상자 > 배송 가능 용량
deliveries[dIdx] -= deliverCap; // 배송 용량만큼만 배송
deliverCap = 0; // 베송 용량 0
break;
}
dIdx--; // 다음 집 방문
}
int pickupCap = cap;
while(pickupCap>0 && pIdx>=0) {
if(pickups[pIdx] <= pickupCap) {
pickupCap -= pickups[pIdx];
pickups[pIdx] = 0;
} else {
pickups[pIdx] -= pickupCap;
pickupCap = 0;
break;
}
pIdx--;
}
}
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 가장 많이 받은 선물 C++ 풀이 및 해설 (1) | 2024.03.16 |
---|---|
[프로그래머스] 도넛과 막대 그래프 C++ 풀이 및 해설 (0) | 2024.03.09 |
[프로그래머스] 순위 검색 C++ 풀이 및 해설 (1) | 2024.02.23 |
[프로그래머스] 양궁대회 C++ 풀이 및 해설 (1) | 2024.02.17 |
[프로그래머스] 이모티콘 할인행사 C++ 풀이 및 해설 (0) | 2024.02.14 |
Comments