[백준] 13458: 시험 감독 (Python)

시험 감독

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

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)

 

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

 

입출력 예제

입력	출력
1 1 1 1	1
3 3 4 5 2 2	7
5 100000 100000 100000 100000 100000 5 7	714290
5 10 9 10 9 10 7 20	10
5 10 9 10 9 10 7 2	13

 

풀이

맨 처음에 떠올린 로직은 다음과 같다. 

1. 총감독관이 해당 시험장의 인원을 모두 감독할 수 있으면 1명만 있으면 되고, 그렇지 않은 경우에는 남은 인원에 대해 필요한 최소 부감독관의 수를 추가로 더한다.
2. 위 연산을 각 시험장에 대해 반복해 필요한 전체 감독 수를 계산한다.

import sys, math
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b, c = map(int, input().split())
ans = 0
for i in a:
	if b >= i:
		ans += 1
	else:
		ans += math.ceil((i - b)/c) + 1
print(ans)

메모리: 145524 KB / 시간: 588 ms

 

위에서는 남은 인원에 대한 계산을 math.ceil() 메소드를 이용해 해결했는데, //와 % 연산자를 이용하여 해결할 수도 있다.

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b, c = map(int, input().split())
ans = 0
for i in a:
	if b >= i:
		ans += 1
	else:
		ans += ((i - b) // c) + 1
		if (i - b) % c != 0:
			ans += 1
print(ans)

메모리: 143400 KB / 시간: 660 ms

메모리 사용량은 줄었지만 소요 시간이 늘었다.

 

혹은 총감독을 먼저 배치한 후 남은 인원이 있는 경우에만 계산하도록 로직을 구성할 수도 있다.

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b, c = map(int, input().split())
ans = 0
for i in range(n):
	a[i] -= b
	ans += 1
	if a[i] > 0:
		ans += a[i] // c
		ans += 1 if a[i] % c != 0 else 0
print(ans)

메모리: 143400 KB / 시간: 744 ms

소요 시간이 더 늘어난 게 이상해서 여러 번 돌렸는데 매번 다르게 나와서 그냥 최소 시간으로 적었다.

왜 이럴까

시간 복잡도: O(n)

공간 복잡도: O(1)