2013 전국 본선 초등2
그리디
상자를 싣고 갈 구간을 보자.
그리디 알고리즘으로 간단하게 풀리는 문제지만 뭐에 대해서 그리디를 적용시킬지 찾는게 쉽지 않다.
결론 부터 말하자면 상자가 트럭에 실려 있는 구간이 짧은 순으로 확인하면 된다. 구간이 같다면 먼저 실을 수 있는 상자를 선택한다. 따라서 상자를 목적지, 출발지 순으로 오름차순 정렬하면 된다.
그 뒤 반복문으로 앞에서 부터 살피면 되는데 이번에 선택된 상자(now)가 트럭에 실려있어야 할 구간을 살피고 모두 실을 수 있다면 now의 cost를, 용량이 초과된다면 남은 용량 만큼을 그 구간에 더해주면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<iostream>
#include<algorithm>
using namespace std;
pair<int, int> pii;
typedef struct In{
int from,to,cost;
}In;
In ins[10001];
// 목적지, 출발지 순으로 정렬
int cmp(In a, In b){
if(a.to!=b.to)
return a.to < b.to;
return a.from < b.from;
}
int box[2001]; // 그 구간에서 트럭이 들고 있는 상자의
int main(){
int ans=0;
int n,c,m;
cin>>n>>c>>m;
for (int i=0; i < m; i++){
scanf("%d %d %d", &ins[i].from, &ins[i].to, &ins[i].cost);
}
sort(ins, ins + m , cmp);
for(int i=0;i<m;i++){
In now = ins[i]; // 이번에 볼 입력 값
int already = 0; // 주어진 구간에서의 최대 상자 수
for (int i = now.from; i < now.to; i++)
already=max(already,box[i]);
// 상자의 최대 갯수를 넘길 수 있기 때문에
// 지금 보고 있는 상자의 개수와 남은 용량중 작은 것을 선택
int add = min(now.cost, c - already);
for (int i = now.from; i < now.to; i++) { //구간에 추가
box[i] += add;
}
ans += add; // 추가한 만큼을 답에 더해줌
}
cout << ans << "\n";
return 0;
}
|
[백준] 2457번 공주님의 정원 (C) (0) | 2020.03.08 |
---|---|
[코드업] 4040 : 펜션 (C) (0) | 2020.03.07 |
[코드업] 3321 : 최고의 피자 (C) (0) | 2020.03.07 |
[코드업] 3301 : 거스름돈 (C) (0) | 2020.03.06 |
[코드업] 3120 : 리모컨 (C) (0) | 2020.03.06 |