13560 : 축구게임

풀이

랑주의 정리!

S[i] = a[1~i]의 합, S[1~k] >= kC2
S[n] = nC2

증명

코드

#include <stdio.h>
#include <algorithm>
int main() {
	int n, i, s = 0, a[10000];
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	std::sort(a, a + n);
	for (i = 0; i < n; i++) {
		s += a[i];
		if (s < (i+1)*i/2) return ~printf("-1");
	}
	printf("%d", s == n*(n-1)/2 ? 1 : -1);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-09-27 12:00

Read more posts by this author