BOJ(백준) 13458[시험 감독]

이번 글에서는 백준 13458번 문제인 “시험 감독”을 함께 해결해 보겠습니다. 이 문제는 각 시험장에서 필요한 감독관의 수를 계산하는 문제입니다.

 

문제 URL : https://www.acmicpc.net/problem/13458

1. 문제 설명

1) 문제 개요

• 여러 개의 시험장이 있고, 각 시험장마다 응시자가 있습니다.

• 한 시험장에 한 명의 주감독관이 필요합니다.

• 부감독관은 여러 명이 있을 수 있으며, 각 부감독관은 C명의 응시자를 감시할 수 있습니다.

• 각 시험장에 필요한 감독관의 총 수를 구하는 것이 목표입니다.

 

2) 입력

• 첫 번째 줄에 시험장의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)

• 두 번째 줄에 각 시험장에 있는 응시자의 수 Ai가 주어집니다. (1 ≤ Ai ≤ 1,000,000)

• 세 번째 줄에 B와 C가 주어집니다. (1 ≤ B, C ≤ 1,000,000)

 

3) 출력

• 각 시험장에 필요한 감독관의 총 수를 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 시험장의 개수 N을 입력받습니다.

• 두 번째 줄에서 각 시험장에 있는 응시자의 수 Ai를 리스트로 입력받습니다.

• 세 번째 줄에서 주감독관이 감시할 수 있는 응시자 수 B와 부감독관이 감시할 수 있는 응시자 수 C를 입력받습니다.

 

2) 감독관 수 계산

• 각 시험장마다 주감독관 1명이 필요하므로 초기 값은 N입니다.

• 각 시험장에 대해 필요한 부감독관 수를 계산하여 총 감독관 수에 더합니다.

• 부감독관 수는 응시자 수에서 주감독관이 감시할 수 있는 인원을 뺀 후, 나머지 인원을 부감독관이 감시할 수 있는 인원으로 나누어 올림 처리하여 구합니다.

 

3. 정답 코드

import sys
import math
input = sys.stdin.readline

# 첫째 줄에 시험장의 개수 N을 입력받음
N = int(input().strip())

# 둘째 줄에 각 시험장에 있는 응시자의 수 Ai를 리스트로 입력받음
A = list(map(int, input().strip().split()))

# 셋째 줄에 B와 C를 입력받음
B, C = map(int, input().strip().split())

# 각 시험장마다 주감독관 1명이 필요하므로 초기 값은 N
ans = N

# 각 시험장에 대해 필요한 부감독관 수를 계산
for i in range(N):
    num = A[i] - B      # 주감독관이 감시할 수 있는 B명을 제외한 나머지 응시자 수
    if num > 0:         # 나머지 응시자가 존재하면
        ans += math.ceil(num / C)  # 부감독관이 필요, 올림을 통해 부감독관 수 계산

# 최종적으로 필요한 감독관의 총 수를 출력
print(ans)

 

4. 코드 설명

1) 입력 받기

• 첫째 줄에서 시험장의 개수 N을 입력받습니다.

• 둘째 줄에서 각 시험장에 있는 응시자의 수 Ai를 리스트로 입력받습니다.

• 셋째 줄에서 주감독관이 감시할 수 있는 응시자 수 B와 부감독관이 감시할 수 있는 응시자 수 C를 입력받습니다.

 

2) 감독관 수 계산

• 초기 값으로 각 시험장에 주감독관 1명씩 할당하여 ans에 N을 저장합니다.

• 각 시험장에 대해 나머지 응시자 수(num)를 계산하고, 부감독관 수를 올림하여 계산하여 총 감독관 수(ans)에 더합니다.

 

3) 결과 출력

• 최종적으로 필요한 감독관의 총 수를 출력합니다.

 

5. Github으로 확인

 

coTest/BOJ/BOJ01_07_03_13458.py at main · pcy4196/coTest

 

시간 복잡도

• 이 문제의 시간 복잡도는 O(N)입니다. 각 시험장에 대해 필요한 감독관 수를 계산하는 루프가 N번 반복되기 때문입니다