BOJ 13560, 축구게임
ProblemSolving ·이 문제는 구현 혹은 수학 문제인 것 같습니다.
풀이
만약 4개의 팀이 있다면 각자 3경기씩 하게 됩니다. 2팀씩 같이 하니까 총 6경기겠죠?
그래서 승점은 n*(n-1)/2 라는 식이 성립하게 됩니다. 이 식이 성립하지 않으면 유효하지 않겠죠?
이 식만 가지고는 정답이 나오지 않습니다. 또 하나 신경 써줘야 할 것이 있습니다.
만약 3 3 0 0 이라는 숫자가 나오면 n*(n-1)/2 라는 식은 성립하지만 1번팀과 2번팀의 싸울 경우도 있는데 둘다 3점을 가질 순 없겠죠?
가능한 숫자의 맥시멈?제일 극적인 숫자는 3 2 1 0 이겠죠?
1번팀이 2,3,4번팀을 다 이기고
2번팀이 3,4번팀을 이기고, 3번팀이 4번팀을 이긴다면 3 2 1 0 이라는 숫자가 나옵니다.
숫자를 정렬해주고 큰 숫자부터 계산해주었습니다.
n,n-1,n-2, …, 1, 0 의 합을 sum값과 따로 계산해주고 sum값이 이 값보다 커지게 된다면 유효하지 않을 것으로 처리해주었습니다.
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,sum,a,guide,arr[10001];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
sort(arr,arr+n);
for (int i = n-1; i >= 0; i--)
{
sum += arr[i];
guide += i;
if (sum > guide)
{
printf("-1");
return 0;
}
}
if (n*(n - 1)/ 2 == sum)
printf("1");
else
printf("-1");
return 0;
}