https://www.acmicpc.net/problem/13458

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다.
i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다.
총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고,
부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고,
부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다.

이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

---

풀이

📍 풀이

필요한 전체 감독관의 수 = ans

각 시험장에 대해
1. B 빼주고 ans++
2. 남은 인원수가 0보다 작거나 같다 → 멈춤
3. C보다 작거나 같다 → 멈추고 ans++
4. 남은 인원수가 C보다 크다 → C 빼주고 ans++, 위 과정 반복

1. B 빼주고 ans++
2. 남은 인원수가 0보다 클 경우에
3. 남은 인원수가 C로 나뉘어 떨어진다 → ans += (남은)/C
4. 남은 인원수를 C로 나눴을 때 나머지가 있다 → ans += (남은)/C + 1

1. B 빼주고 ans++
2. 남은 인원수가 0보다 클 경우에
3. ans += { (남은 인원수+1) / C+1 }

📍 주의사항

1. 변수가 최대값을 수용할수 있는가?

int로 선언하면 최대값 2147483647
B=1, C=1, N=1,000,000, Ai=1,000,000 처럼 특수한 경우엔 ans가 1,000,000^2 가 되면서 int범위 초과함!!
→ int 대신 long long 으로.

📍 코드

#include <iostream>
#define MAX 1000000
#define endl "\n"
#define lld long long
using namespace std;

int A[MAX];
int N, B, C;
lld ans = 0;

void Input() {
	// 시험장의 갯수 N
	cin >> N;

	// 각 시험장의 응시자 수
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	// B와 C
	cin >> B >> C;
}

void How_Many_Supervisors(int candidates) {
	candidates -= B;
	ans++;

	if (candidates > 0)
		ans += ((candidates - 1) / C + 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Input();
	for (int i = 0; i < N; i++) {
		How_Many_Supervisors(A[i]);
	}

	cout << ans << endl;
	return 0;
}