문제 링크
문제
문제의 조건을 만족하면서 배송할 수 있는 택배의 최대 개수를 구하는 문제
- 조건 1: 박스를 트럭에 실으면, 박스는 받는 마을에서만 내린다.
- 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
- 조건 3: 박스들 중 일부만 배송할 수도 있다.
풀이
문제를 보고 금방 내리는 순서가 빠른 것부터 실는 게 이득이라는 생각을 할 수 있었다. 난이도에 비해 발상이 쉽다고 생각하면서 코드를 짜보고 제출해보고 나서야 비로소 문제점들을 알 수 있었다.
풀이 방법은 얼추 알겠는데 어떻게 구현해야할지 감이 잘 안 잡혀서 고생을 했다.
삽질1
처음에는 각 지점별로 내릴 수 있는 택배의 수를 저장하고, 해당 지점에 방문하면 택배를 내렸다고 가정하여 answer을 증가시키고 nowCount(현재 트럭에 있던 택배의 양)을 감소시키는 방법을 생각하고 구현했다.
이렇게 하면 다음과 같은 경우 제대로 결과를 계산하지 못한다.
5 4
5
2 4 1
4 5 3
1 5 1
3 4 2
1 2 2
answer: 9도착지점 순서로 정렬해서 확인하며,
1. 현재 트럭의 용량이 비어있으면 실는다고 가정 후 해당 택배의 도착지점의 값을 업데이트
2. 현재 위치에서 내릴 택배가 있으면 내리고 트럭의 현재 용량을 업데이트
3. 현재위치에서 실을 수 없는 위치인 경우(이미 지나친 경우)는 무시
다음의 작업을 매 위치마다 반복해주면 될 것이라고 생각했다.
이렇게 했을 때 트럭의 용량을 최대로 확인하지 못 한다.
위의 예시에 이 풀이를 적용하면 3번째 택배(1 5 1)를 실을 수 없다고 판단한다.
풀이 1
그냥 복잡하고 비효율적이더라고 N값이 2000이하로 꽤 만만한 수이기 때문에 정직하게 구현하기로 했다.
- 실려있는 택배 중 i번째에서 내리는 택배를 다 내린다.
- i번째에서 보내는 택배를 일단 다 실는다.
- 트럭 용량을 맞춘다.
priority_queue를 이용해서 트럭에 실려 있는 택배를 관리한다. 실려있는 택배는 내리는 순서가 빠른 순서대로 확인한다.
트럭에 실려있는 택배의 양을C이하로 관리한다. -> 매번queue를 비우고 가능한 만큼만 다시 채운다.
무식하게 구현해버렸는데 통과됐다.
하지만 다른 사람 풀이를 보니 시간복잡도 차이가 상당했다. 내 풀이가 정상적인 풀이가 아니라는 것을 알아차릴 수 있었다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"
using namespace std;
int N, C, M;
void Solve() {
cin>>N>>C;
cin>>M;
vector<pair<int,int>> V[2020];
int a,b,c;
int nowLoc = 0, nowCount = 0, answer = 0, idx = 0;
for(int i=0; i<M; i++){
cin>>a>>b>>c;
V[a].push_back({b,c});
}
for(int i=0; i<=N; i++){
sort(V[i].begin(), V[i].end());
}
priority_queue<pair<int,int>> PQ;
for(int i=0; i<=N; i++){
//i번째에서 내리는 택배를 다 내린다.
while(!PQ.empty() && PQ.top().first == -i){
//cout<<i<<" "<<PQ.top().second<<endl;
answer+=PQ.top().second; PQ.pop();
}
//i번째에서 보내는 택배를 일단 다 실는다.
for(int j=0; j<V[i].size(); j++){
PQ.push({-V[i][j].first, V[i][j].second});
}
//트럭 용량을 맞춘다.
vector<pair<int,int>> V;
nowCount = 0;
while(!PQ.empty() && nowCount<C){
pair<int,int> p = PQ.top(); PQ.pop();
int count = min(C-nowCount, p.second);
nowCount+=count;
V.push_back({p.first, count});
}
while(!PQ.empty()) PQ.pop();
for(int i=0; i<V.size(); i++) PQ.push(V[i]);
}
cout<<answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
Solve();
return 0;
}풀이 2
일반적인 풀이이다.
삽질 했던 것과 꽤 유사하다.
핵심은 트럭이 i번째를 지날 때 트럭에 실려있는 택배의 양이 얼마인지 관리하는 것이다.
택배가 start에서 실어서 end에서 내린다고 가정할 때, 해당 택배를 얼마나 실을 수 있는지 결정하는 것은 cnt[start] 에서 cnt[end-1] 까지 중 최댓값과 허용용량의 차이이다.
즉 택배가 가야하는 구간에서 트럭이 가장 많이 택배를 실었을 때에도 용량이 남아있다면 그만큼 실을 수 있다.
이렇게 실을 수 있는 양을 계산하면 택배를 실었다고 가정하고 해당 구간을 업데이트 해준다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl "\n"
using namespace std;
int N, C, M;
int cnt[2020];
struct Box{
int start, end, count;
};
bool cmp(const Box& a, const Box& b){
return a.end < b.end;
}
void Solve() {
cin>>N>>C>>M;
vector<Box> V;
int a,b,c, maxCount, availCount, answer=0;
for(int i=0; i<M; i++){
cin>>a>>b>>c;
V.push_back({a,b,c});
}
sort(V.begin(), V.end(), cmp);
for(int i=0; i<M; i++){
maxCount = 0;
for(int j = V[i].start; j<V[i].end; j++){
maxCount = max(maxCount, cnt[j]);
}
availCount = min(V[i].count, C - maxCount);
for(int j = V[i].start; j<V[i].end; j++){
cnt[j]+=availCount;
}
answer+=availCount;
}
cout<<answer;
오래 붙잡았는데 풀어서 다행이다.
