Baekjoon 13458 시험감독

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

소스결과 5888 KB / 12 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘, 수학

 

설명

총 감독관이 a명을 감시하고 부 감독관이 b 명을 감시할 때 모든 시험장에서 필요한 감독관의 수를 구하여라.

 

알고리즘 자체는 쉽다. 각 시험장에는 총 감독관 1명만이 필수로 배치 되어야하고, 나머지 인원을 감시하기 위해서 부 감독관이 배치가 된다.

각 시험장에 총 감독관을 배치 후에 남은 인원 수를 부 감독관이 감시 할 수 있는 수로 나눈 후, 나머지가 존재 한 다면 추가로 한명을 더 배치하면 된다.

다만, 결과 값이 정수 범위를 넘어갈 수 있다. ( b 와 c가 1이고, n = Ai = 1,000,000 인 경우 10 ^ 16 , int 는 2 * 10 ^ 10 까지 )

범위 설정에 유의하자

 

알고리즘

1. 시험장 개수, 응시자 수, b, c를 입력 받는다.

2. 각 시험장의 응시자 수 에 대해서 b를 뺀 후 결과값을 1 늘린다.

3. b 를 뺸 응시자 수가 0보다 큰 경우, c로 나눈 몫 만큼을 결과 값에 더하고 나머지가 존재하면 추가적으로 1 더 더한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;

int applicant[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int tcc, admin, submin;
	long long res = 0;

	cin >> tcc;

	for (int i = 0; i < tcc; i++)
		cin >> applicant[i];

	cin >> admin >> submin;

	for (int i = 0; i < tcc; i++)
	{
		applicant[i] -= admin;
		res++;
		
		if (applicant[i] <= 0)
			continue;

		res += applicant[i] / submin;
		res = res + (applicant[i] % submin ? 1 : 0);
	}

	cout << res;

	return 0;
}