백준 문제 중 13458번, 그리디, ‘시험감독’

백준 문제 중 13458번 with python

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)

출력

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

---

풀이

조건만 잘 따진다면 매우 간단한 문제이다. 그런데도 정답률이 상당히낮다. 꼼꼼한 반례 체크가 핵심인 문제였다.

코드의 흐름은 다음과 같다.

1. 같은 응시자수에 대한 필요한 감독수는 변하지 않으니 각가의 응시자수에 필요한 감독수를 저장할 딕셔너리 DP를 선언한다. (총감독수가 무조건 있어야 하므로 1로 초기화)
2. 모든 시험장에 대해 계산을 진행하는데 이미 계산한 적이 있는 응시자수 즉 dp의 값이 1이 아니라면 건너뛴다.
3. 응시자수가 총 감독관이 감시할 수 있는 수보다 적을 경우도 고려한다.
4. 응시자수가 총 감독관이 감시할 수 있는 수보다 많다면 부 감독관이 필요하고, c로 나누어 떨어질때와 아닐때를 나누어 계산한다.
5. 모든 시험장의 계산이 종료되면 dp의 모든 성분을 더해 출력한다.

이를 코드로 구성하면 아래와 같다.

n = int(input())
a_list = list(map(int, input().split()))
b, c = map(int, input().split())

 # 각 응시자의 수를 키로 감독관의 수를 값으로 할 딕셔너리 선언
dp = {a_list[i]:1 for i in range(n)}

for i in range(n):
     # 이미 계산된 응시자수라면 건너뜀
    if dp[a_list[i]] != 1:
        continue
     # 부 감독관이 필요 없는 경우는 건너뜀
    elif a_list[i] - b > 0:
        if (a_list[i] - b)%c == 0:
            dp[a_list[i]] += (a_list[i] - b)//c
        else:
            dp[a_list[i]] += (a_list[i] - b)//c + 1

ans = 0
for i in range(n):
    ans += dp[a_list[i]]

print(ans)

5
10 9 10 9 10
7 2
13