[백준] 삼성 SW 역량 테스트 기출 문제 13458번 : 시험 감독 (파이썬/Python)

[백준] 삼성 SW 역량 테스트 기출 문제 13458번 : 시험 감독 (파이썬/Python)

전체 정답 코드 및 설명

정답 코드

import sys
input = sys.stdin.read

# 입력 받기
data = input().split()
N = int(data[0])  # 시험장의 개수
A = list(map(int, data[1:N+1]))  # 각 시험장의 응시자 수
B, C = map(int, data[N+1:])  # B: 총감독관 감시 가능 인원, C: 부감독관 감시 가능 인원

# 결과 계산
result = N  # 각 시험장마다 최소 1명의 총감독관 필요
for i in range(N):
    remaining = A[i] - B  # 총감독관이 감시 후 남은 응시자 수
    if remaining > 0:  # 남은 응시자가 있으면 부감독관 배치
        result += (remaining + C - 1) // C 

# 결과 출력
print(result)

문제 설명

각 시험장에 꼭 1명의 총감독이 있어야한다. 이 점을 주의하자.

1번째 풀이

import sys
input = sys.stdin.readline

# 시험장의 개수 1 <= N <= 1,000,000
N = int(input())
# A[i] 는 각 시험장에 있는 응시자의 수
A = list(map(int, input().strip().split()))
# B : 총감독관이 한 시험장에서 감시할 수 있는 응시자 수 
# C : 부감독관이 한 시험장에서 감시할 수 있는 응시자 수 
B, C = map(int, input().strip().split()) 

# 각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수 출력
result = N # 각 시험장에 총감독관이 들어가야함 
for i in range(N):
    A[i] -= B # 각 시험장에 총감독관이 체크할 수 있는 인원 제외시키기
for i in range(N):
    temp = A[i]
    while temp > 0:
        # print("(3) temp = ", temp, "i = ", i, "result = ", result)
        temp = temp - C
        result = result + 1
        # print("(4) temp = ", temp, "i = ", i, "result = ", result)

print(result)

처음에 모든 값을 입력 받고, 각 시험장에 총 감독관을 배치해야하기 때문에 result 결과값을 가지는 변수를 N(시험장 수) 로 설정하였고, 각 시험장에 총감독관이 감독할 수 있는 인원수를 빼주었다.

그 후에 A 배열을 하나씩 순회하였다. 순회할 때마다 temp 가 0보다 크다면 temp 에 C 를 빼주고 result 값에 +1 해주었다.

이 경우 시간 초과라는 결과로 문제 풀이에 실패하였다.

2번째 풀이

import sys
input = sys.stdin.readline

# 시험장의 개수 1 <= N <= 1,000,000
N = int(input())
# A[i] 는 각 시험장에 있는 응시자의 수
A = list(map(int, input().strip().split()))
# B : 총감독관이 한 시험장에서 감시할 수 있는 응시자 수 
# C : 부감독관이 한 시험장에서 감시할 수 있는 응시자 수 
B, C = map(int, input().strip().split()) 
# print("처음 A : ",A)
# 각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수 출력
result = N # 각 시험장에 총감독관이 들어가야함 
for i in range(N):
    A[i] -= B # 각 시험장에 총감독관이 체크할 수 있는 인원 제외시키기
# print("총 감독관이 볼 수 있는 응시자 수를 뺌",A, "result = ", result)
for i in range(N):
    temp = A[i]
    q, r = divmod(temp, C)
    result += q
    if r > 0:
        result += 1

print(result)

1번째 풀이와 다른 점은 temp 를 C로 나누고 몫을 result에 더한 후 나머지가 존재하다면 +1 해주는 방법으로 풀었다. 하지만 제출 결과 틀렸습니다 가 나왔고, 확인을 위해서 모든 예제를 넣어보았지만 정답이 나왔기 때문에 어디가 잘못되었는 지 몰라 코드를 다시 리팩토링을 진행하였다.

3번째 풀이(정답)

import sys
input = sys.stdin.read

# 입력 받기
data = input().split()
N = int(data[0])  # 시험장의 개수
A = list(map(int, data[1:N+1]))  # 각 시험장의 응시자 수
B, C = map(int, data[N+1:])  # B: 총감독관 감시 가능 인원, C: 부감독관 감시 가능 인원

# 결과 계산
result = N  # 각 시험장마다 최소 1명의 총감독관 필요
for i in range(N):
    remaining = A[i] - B  # 총감독관이 감시 후 남은 응시자 수
    if remaining > 0:  # 남은 응시자가 있으면 부감독관 배치
        result += (remaining + C - 1) // C  # 필요한 부감독관 수: 올림 처리

# 결과 출력
print(result)

1. read 로 입력된 것을 모두 읽고, N 와 A, B, C 를 나누었다.
2. result 를 N 으로 설정한다. 각 시험장에 총 감독관을 한명씩 배치한 것이다.
3. 다음으로 for 문을 이용해 A 배열을 순회한다.
4. for 문 내에서 총감독관이 감시 할 수 있는 인원 수를 빼고 남은 응시자가 있을 경우 result 에 (남아 있는 수 // 부감독관이 감시 할 수 있는 인원) 값을 더해주는 데 이는 나머지가 있을 경우를 대비하여 남아 있는 수에 부감독관이 감시할 수 있는 인원 - 1 값을 더하고 나누었다.

총감독관이 들어가고도 인원수가 남을 경우 <<< 이 경우에 음수일 경우를 고려하지 않은 것.