티스토리 뷰

알고리즘 관련/BOJ

BOJ)13560 Football

JASON 자손9319 2017. 2. 20. 15:02

문제: icpc.me/13560 


n개의 축구 팀이 존재할 때 각 축구 팀의 승수가 주어진다. 각 축구팀들 끼리는 무조건 한번의 경기가 열리며 승패가 반드시 갈린다고 할 때 주어진 축구팀의 승수의 셋이 valid 한지의 여부를 묻는 문제이다.


우리는 승수를 받은 뒤 sort해준 다음 승수가 적은 팀부터 큰 팀으로 볼 건데 승수가 작은 팀은 승수가 현재 주어진 셋에서 큰팀한테 졌다고 가정하여 팀을 하나씩 삭제하는 방법으로 그리디하게 접근해줄 것이다.


도중에 내가 이긴팀이 남은 팀보다 많거나 내가 이긴팀의 수가 0보다 작은 경우가 생기면 invalid하다고 판단해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
#define MAX_N 10000
using namespace std;
int c[MAX_N + 1], n, f;
int main() {
    scanf("%d"&n);
    for (int i = 1; i <= n; i++)
        scanf("%d"&c[i]);
    sort(c + 1, c + + n);
    for (int i = 1; i <= n; i++) {
        if (c[i] > n - i || c[i] < 0) {
            f = 1;
            break;
        }
        for (int j = 0; j < n - c[i] - i; j++)
            c[n - j]--;
        sort(c + i + 1, c + + n);
    }
    printf("%d\n", f ? -1);
    return 0;
}
 
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9169 나는 9999번 문제를 풀 수 있다  (0) 2017.02.20
BOJ)1017 소수 쌍  (0) 2017.02.20
BOJ)13560 Football  (0) 2017.02.20
BOJ)12019 동아리방 청소!  (0) 2017.02.17
BOJ)1671 상어의 저녁식사  (0) 2017.02.16
BOJ)1867 돌멩이 제거  (0) 2017.02.16
댓글
댓글쓰기 폼