3985번: 롤 케이크
첫째 줄에 롤 케이크의 길이 L (1 ≤ L ≤ 1000)이 주어진다. 둘째 줄에는 방청객의 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 각 방청객 i가 종이에 적어낸 수 Pi와 Ki가 주어진다. (1 ≤ Pi ≤ Ki
www.acmicpc.net
가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호는 입력으로 주어지는 l과 r의 차이가 큰 값을 출력하면 됩니다.
하지만 앞의 방청객이 원하는 조각을 받으면 뒤의 방청객은 받지 못하는 상황이 있을 수 있습니다.
입력으로 1번 방청객부터 N번 방청객까지 원하는 조각의 범위가 주어지면 list에 바로 방청객의 번호를 저장해줍니다.
이때 번호가 이미 저장되어있으면 저장하지 않고, 번호를 저장한 횟수를 num에 저장하여 num[i]이 가장 큰 방청객의 번호를 출력해주시면 됩니다.
|
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
|
#include <iostream>
using namespace std;
int list[1001], num[1001];
int L, N;
void func() {
int maxlength = 0;
int maxidx = 0;
for (int i = 1; i <= N; i++) {
if (maxlength < num[i]) {
maxlength = num[i];
maxidx = i;
}
}
cout << maxidx << '\n';
}
void input() {
int maxlength = 0;
int maxidx = 0;
int l, r;
cin >> L >> N;
for (int i = 1; i <= N; i++) {
cin >> l >> r;
if (maxlength < r - l) {
maxlength = r - l;
maxidx = i;
}
for (int j = l; j <= r; j++) {
if (list[j]) continue;
list[j] = i;
num[i]++;
}
}
cout << maxidx << '\n';
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 3085 사탕 게임 (0) | 2021.02.26 |
|---|---|
| boj 8320 직사각형을 만드는 방법 (0) | 2021.02.25 |
| boj 2116 주사위 쌓기 (0) | 2021.02.25 |
| boj 10163 색종이 (0) | 2021.02.24 |
| boj 20055 컨베이어 벨트 위의 로봇 (0) | 2021.02.23 |
