[Python 알고리즘] 백준 13458번 : 시험 감독

문제

• 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.
• 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.
• 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

입력

• 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
• 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.
• 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

# Case 1
1
1
1 1

# Case 2
3
3 4 5
2 2

# Case 3
5
1000000 1000000 1000000 1000000 1000000
5 7

# Case 4
5
10 9 10 9 10
7 20

# Case 5
5
10 9 10 9 10
7 2

출력

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

# Case 1
1

# Case 2
7

# Case 3
714290

# Case 4
10

# Case 5
13

내가 제출한 풀이 - 정답

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
b, c = list(map(int, sys.stdin.readline().strip().split()))
res = 0

for i in range(n):
    # 총 감독
    res += 1
    mok = a[i] - b

    # 부 감독
    if mok > 0:
        if mok == c:
            res += 1
        elif c == 1 or mok % c == 0:
            res += mok // c
        elif mok > 0:
            res += (mok // c) + 1

print(res)

정답을 맞긴 헀지만 계속 반례를 찾다가 하나하나씩 추가되면서 코드가 매우 더러워졌다. 그냥 총감독관에 대한 걸 미리 계산하고 나머지 응시자 수로 컨트롤 했으면 좀 더 깔끔한 코드가 됐을 거 같다.

정답

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
b, c = list(map(int, sys.stdin.readline().strip().split()))

# 총감독 수
res = n

for num in a:
    num -= b

    if num < 0:
        continue

    # 부 감독
    if num % c == 0:
        res += num // c
    else:
        res += num // c + 1

print(res)

문제풀이

• 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

문제 조건을 보게 되면 시험장 개수 = 총 감독관의 개수라는 것을 알 수 있다.

그러면 응시자 수(a) - 총 감독관이 볼 수 있는 응시자 수(b)를 한 다음 부감독관이 볼 수 있는 응시자 수(c)로 나누면 총 몇 명이 필요한지 알 수 있게 된다.

 

(a - b) // c를 하면 부 감독관이 몇 명 필요하게 되는지 알 수 있는데, 0으로 나누어 떨어지지 않으면 + 1을 하는 이유는

다음과 같다.

1. a = 8, b = 4, c = 2라고 가정해보자
2. (8 - 4) // 2 = 2이다. 그러면 총 2명의 부감독관이 필요하는 게 맞다.
3. 근데 a = 9라는 가정하에 다시 봐보자
4. (9 - 4) // 2 = 2이다. 하지만 나머지 1이 남기 때문에 1명을 위해서 부감독관을 1명 추가해야하는 것이다.

삼성역량 테스트에 나온 문제라고 한다. 그런 거 치고 매우 쉽고 간단한 문제지만 풀었다는 거에 의의를 둬 자신감을 찾도록 하자!