BOJ 1206 - 사람의 수
오랜만에 푸는 수학 문제(사칙연산 안해본지 2년지남)라 쉬운건데도 헤맸다.
이 문제가 까다로운 점은 소수점 처리에 있다. 하지만 이는 정수를 이용한 계산으로 변형이 가능하다.
항상 자리수까지 주어지므로 처럼 을 곱해서 다룬다고 생각해보자.
사람이 명이 있다면 항상 모든 점수를 만들 수 있으므로 사람수는 최대 명이다. 예를 들어, 라는 평균 점수는 이고 명이 총합 점을 내게 되면 만들어지기 때문이다.
현재 확인하는 사람수가 라고 하자. 그럼 사람이 내는 점수에도 을 곱하므로 까지의 범위가 총점이 될 것이다.
그럼 이 점수의 집합을 라고 하자.
그럼 우린 모든 개의 점수에 대해서 임을 만족하는 가 내에 존재하는지 검사하면 된다.
이는 정도가 된다.
아래의 코드는 내에서 존재하는 가 있는지 단순히 모두 검사하는 것이지만 간단한 수식으로 을 뗄 수 있다.
void solve() {
int n;
cin >> n;
vi a;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
auto v = spliti<int>(s, ".");
a.pb(v[0] * 1000 + v[1]);
}
for (int i = 1; i <= 1000; i++) {
// S = {a | 0 ~ i * 10000 까지 1000 단위로}
// 이 총점을 k라고 할때, 1 <= j <= n 을 만족하는 모든 정수 j에 대해
// a[j] = S_x / i 를 만족하는 x가 존재하는가?
int success = 1;
for (int j = 0; j < n; j++) {
int check = 0;
for (int sum = 0; sum <= i * 10000; sum += 1000) {
if (a[j] == sum / i) {
check = 1;
break;
}
}
if (!check) {
success = 0;
break;
}
}
if (success) {
cout << i;
return;
}
}
}
Comments