https://www.acmicpc.net/problem/2262
2262번: 토너먼트 만들기
월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러
www.acmicpc.net
주어지는 랭킹은 중복이 없으며, 랭킹이 높은 사람 (숫자가 낮은 사람)이 무조건 이깁니다.
문제에서 요구하는 것은 이 토너먼트에서 각 경기에 임하는 선수들의 랭킹의 차이의 합이 최소가 되도록 대진을 구성해야합니다.
랭킹이 낮을수록 (숫자가 클수록) 랭킹의 차이의 합이 커지므로 랭킹이 낮은 선수는 빠르게 경기를 하는 것이 이득입니다.
따라서 랭킹이 낮은 선수부터 차례대로 본인의 좌우 선수들 중 랭킹이 낮은 선수와 경기를 하게 만들면 랭킹의 차이의 합이 최소가 됩니다.
|
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
|
#include <iostream>
#include <algorithm>
#define MAX 256
using namespace std;
int list[MAX];
int N;
void func() {
int ans = 0;
for (int i = N; i > 1; i--) {
int j = 0;
for (; j <= N; j++) {
if (i == list[j]) break;
}
ans += (i - max(list[j - 1], list[j + 1]));
for (; j < N; j++) {
list[j] = list[j + 1];
}
N--;
}
cout << ans << '\n';
}
void input() {
cin >> N;
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 16120 PPAP (0) | 2021.10.16 |
|---|---|
| boj 13904 과제 (0) | 2021.09.30 |
| boj 1826 연료 채우기 (0) | 2021.02.22 |
| boj 8980 택배 (0) | 2021.02.16 |
| boj 11000 강의실 배정 (0) | 2021.02.16 |