[백준/BOJ] 13458번 시험 감독 (C/C++)

백준 온라인 저지(BOJ) 13458번 시험 감독
https://www.acmicpc.net/problem/13458

13458번: 시험 감독

* 사용언어 : C언어, C++

 

1. 문제

N개의 시험장에 있는 각각의 응시자들을 감독하기 위한 최소 감독관 수를 출력
총 감독관은 B명 감시할 수 있고 시험장에 1명만 있어야 하고,
부 감독관은 C명 감시할 수 있고 시험장에 여러 명 있어도 됨

 

2. 풀이

우선 n, a(배열), b, c 를 각각 선언하고 입력을 받습니다.
그리고 출력할 감독관 수를 cnt 라고 선언한 뒤 총 감독관 수인 n 으로 초기화하였습니다.
 
그리고 각 a(시험장)에 있는 응시자 수를 -b 씩 차감하였습니다.
(n명의 총 감독관이 각 시험장의 b명을 감독할 수 있으므로)

long long cnt = n;
for (int i = 0; i < n; ++i) {
	a[i] -= b;

 
b를 뺀 후에도 a[i] 값이 양수라면, (a[i] / c)의 올림 값 만큼 부 감독관이 필요합니다.
이를 cnt 에 더하는 방식으로 구현하였습니다.
 
ceil 함수를 사용하지 않고 직접 구현해보려고 시도하다가 구글링해봤는데
(x / y) 의 올림 값이 (x + y - 1) / y 와 같다는 것을 알게 되어 사용해봤습니다.
(그냥 math.h 라이브러리의 ceil 함수를 사용하셔도 됩니다)
 
그리고 감독관의 수(cnt)는 최악의 경우 1,000,000 * 1,000,000 가 되므로 int 형으로 표현이 안 됩니다.
따라서 long long (2^64) 으로 처리하였습니다.
(각 시험장에 100만 명, 감독관은 1명만 감독 가능한 경우)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
13458_시험 감독
5016kb	168ms
*/
#include <cstdio>

int a[1000000];

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, b, c;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	scanf("%d %d", &b, &c);

	long long cnt = n;
	for (int i = 0; i < n; ++i) {
		a[i] -= b;
		if (a[i] > 0) cnt += (a[i] + c - 1) / c;
	}

	printf("%lld\n", cnt);
	return 0;
}