1. 총감독관은 반드시 1명 있어야 한다. (없어도 안되고, 2명 이상이 있어도 안된다.)
2. 부감독관은 있어도 되고 없어도 된다.
3. 최악의 경우(N: 1,000,000 , Ai가 모두 1,000,000, B: 1, C: 1 인 경우) 필요한 감독관의 수가 1,000,000 * 1,000,000 명이 될 수 있으므로 int형 변수를 이용해 결과를 출력할 경우 틀리게 된다.
풀이
먼저 총감독관은 각 방마다 무조건 1명씩 있어야 하므로 N명이 필요하다.
이제 각 방에서 감시해야할 응시자 수는 Ai - B 가 된다.
나머지 시험 응시자들은 부감독관들이 모두 감시해야 한다.
각 방의 (Ai - B) 값을 "부감독관이 감시할 수 있는 응시자 수"로 나누어 주면,
각 방에 남은 응시자들을 모두 감시하기 위해 필요한 부감독관의 수를 구할 수 있다.
단, 이 때 나누어 떨어지는 경우는 괜찮지만 그렇지 않는 경우에 1을 더해줘야 하는 번거로움이 있는데, 이 부분은 C - 1을 더해서 나누어 줌으로써 편하게 계산할 수 있다.
코드
#include <cstdio>
// long long을 편하게 사용하기 위해 llint로 설정
typedef long long llint;
// N(시험장의 수),
// B(총 감독관이 한 방에서 감시할 수 있는 응시자의 수),
// C(부감독관이 한 방에서 감시할 수 있는 응시자의 수)
int n, b, c;
// 각 시험장에 있는 응시자의 수를 저장할 배열
int a[1000000];
// 정답을 저장할 변수(필요한 감독관 수의 최소값, long long 형)
llint ans = 0;
int main() {
// 시험장(방)의 개수를 입력받는다.
scanf("%d", &n);
// 각 방에 있는 응시자 수를 입력받는다.
for(int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// 한 방에서 감시할 수 있는 응시자 수를 입력 받는다.(총감독관, 부감독관)
scanf("%d %d", &b, &c);
// (1) 총감독관
// 총 감독관이 감시할 수 있는 응시자 수를 뺀다.
// 뺄 때, 음수가 되지 않도록 조건이 필요하다.
for(int i = 0; i < n; i++) {
if(a[i] >= b)
a[i] -= b;
else //(방의 인원 < 감시할 수 있는 응시자수)인 경우
a[i] = 0;
}
// 총감독관은 반드시 각 방에 1명씩 필요하므로 총 N명이 반드시 필요하다.
ans = n;
// (2) 부감독관
// 정수형 나눗셈이므로 나누어 떨어지지 않으면,
// 몫에 1을 더한 값이 응시자들을 모두 감시하기 위해 필요한 부감독관의 수가 된다.
// 하지만 그렇게 하지 않아도, c - 1을 더해주고 나누면
// 나누어 떨어지는 경우, 그렇지 않은 경우 모두 올바르게 답을 구할 수 있다.
for(int i = 0; i < n; i++) {
ans += (llint)((a[i] + c - 1) / c);
}
// long long형이므로 %lld로 출력해준다.
printf("%lld\n", ans);
return 0;
}
