https://www.acmicpc.net/problem/15553
N명의 친구가 방에 방문할 예정이고, 친구가 있는 시간에는 난로가 켜져 있어야 합니다.
난로는 K번까지 켤 수 있으며, 난로가 켜져있는 최소 시간을 구해야합니다.
이 문제는 인접한 시간의 간격을 이용하여 그리디하게 문제를 풀 수 있습니다.
우선 N명의 친구가 방문할때는 난로가 켜져있어야 하기 때문에 N번의 난로를 모두 켜주도록 합니다.
여기서 난로가 켜져있는 시간은 N이고, N번 난로를 켠 상태입니다.
난로는 최대 K번까지만 켤 수 있으므로 "친구가 나간 시간 ~ 다른 친구가 들어온 시간"의 간격 동안에는 난로가 추가로 켜져있어야 합니다.
즉 list[i] - (list[i - 1] + 1) 시간 동안에는 추가로 난로가 켜져 있어야 합니다.
그렇다면 이 시간들을 작은 값부터 더해준다면 답을 구할 수 있습니다.
저는 그 시간들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬했습니다.
이후에는 cnt = K가 될때까지 벡터에 있는 시간들을 추가로 더해주도록 합니다.
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100001
using namespace std;
vector<int> v;
int list[MAX];
int N, K;
void func() {
for (int i = 1; i < N; i++) {
v.push_back(list[i] - (list[i - 1] + 1));
}
sort(v.begin(), v.end());
int ret = N;
int cnt = N;
int idx = 0;
while (cnt > K) {
ret += v[idx++];
cnt--;
}
cout << ret << '\n';
}
void input() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Greedy' 카테고리의 다른 글
| boj 2513 통학버스 (0) | 2024.07.14 |
|---|---|
| boj 1437 수 분해 (0) | 2024.07.12 |
| boj 23559 밥 (0) | 2024.07.11 |
| boj 2140 지뢰찾기 (0) | 2024.07.10 |
| boj 1132 합 (0) | 2024.07.08 |