풀이
랑주의 정리!
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이