문제 13458.시험 감독(문제집)

문제설명

 

시험을 치루는 응시자들이 각 시험장에 있다.

응시자를 감시하기 위해 총감독관과 부감독관은 시험장에 배치되어야 한다.

이 때, 총감독관은 각 시험장에 항상 1명이 있어야 하며, 부감독관은 여럿이 있어도, 없어도 된다.

 

총감독관은 B명을 감시할 수 있고, 부감독관은 C명을 감시할 수 있다.

 

모든 응시자들을 감시하는데 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

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

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

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

입력 예제

3
3 4 5
2 2

 

Tips

1. 본감독관은 항상 시험장에 한 명씩 있다. 변동이 없는 요소이기 때문에 부감독관의 수를 구하기 전 미리 계산을 한다.

2. 모든 응시자를 감시해야 하니 한 방에 x.xxxx명의 부감독관이 필요하다면 아래 소수점을 올림해서 인원 수를 구하면 된다.

3. 항상 int를 조심하자 간단한 알고리즘 문제가 틀린다면 10에 9는 longlong을 쓰지 않았기 때문이다.

4. 배열은 int기준 10^5 정도가 넘으면 메모리 초과가 발생한다. 이러한 문제가 발생할 때, vector 자료형을 사용하면 손쉽게 메모리 초과 오류에서 벗어날 수 있다.(다음 코드와 같이)

정답 코드

#include <iostream>
#include <vector>			// vector 
#include <cmath>			// ceil()

#define MAXN 1000000

using namespace std;

int main(void) {

	int N;
	vector<int> v(MAXN);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	int B, C;
	cin >> B >> C;

	// 항상 int 범위를 생각하자.
	long long main_inspector = N;			
	long long sub_inspector = 0;
	for (int i = 0; i < N; i++) {
		v[i] -= B;

		if (v[i] > 0) sub_inspector += ceil((double)v[i] / C); 
	}

	cout << main_inspector + sub_inspector << '\n';

	return 0;
}