[BJ13458] 시험 감독

🚩 문제 설명

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

13458번: 시험 감독

 

⏱️ 시간 복잡도
▪ 각 시험장의 길이만큼 반복문을 돈다.
▪ 따라서 O(N)

◾ 간단한 사칙연산으로 풀 수 있는 문제입니다.

◾ 각 시험장에 필요한 총 감독관의 최소값을 출력하면 됩니다.

 

 

 

---

 

 

 

✅ 입출력

1. n : 시험장 개수
2. a : 각 시험장에 있는 응시자의 수
3. b c : 총감독관 감시 가능 응시자 수, 부감독관 감시 가능 응시자 수
return 필요한 감독관의 최솟값

✔️ 예제 1

3
3 4 5
2 2

7

 

✔️ 예제 2

5
1000000 1000000 1000000 1000000 1000000
5 7

714290

 

✔️ 예제 3

8
5 10 30 235 1 23 24 101
10 3

131

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from math import ceil

sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline

n = int(input())  # 시험장 수
a = list(map(int, input().split()))  # 각 시험장에 있는 응시자의 수
b, c = map(int, input().split())  # 총감독관, 부감독관 감시 가능 수

if __name__ == '__main__':
    ans = 0

    # 필요한 감독관의 수 구하기
    for x in a:
        if x <= b:  # 총감독관만 있으면 되는 시험장
            ans += 1
        else:  # 부감독관도 필요한 시험장
            ans += 1  # 총감독관
            ans += ceil((x - b) / c)  # 부감독관

    print(ans)

💬 Point

➡️  각 시험장의 수 만큼 반복문을 돌아야합니다.
➡️  총 시험감독관은 각 한명씩 꼭 필요합니다. 부감독관을 따로 처리해줘야합니다.

◾ 총 감독관만 있으면 되는 시험장은 총감독관이 감시할 수 있는 응시자의 수보다 같거나 적습니다.

따라서 x <= b 의 조건을 만족한다면 ans += 1 을 하여 총감독관의 수를 더해줍니다.

 

◾ 부감독관이 추가적으로 필요한 시험장은 x > b 의 조건을 만족하게 됩니다.

각 시험장마다 총 감독관은 꼭 필요하니 ans += 1 은 해줍니다.

그리고 각 x 마다 총 감독관이 감시할 수 있는 응시자의 수를 빼줍니다. 그러면 (x-b) 가 됩니다.

부감독관은 c 만큼 응시자를 감독할 수 있습니다.

따라서 c 만큼 나눠줘야지 총 몇명의 부감독관이 필요한지 알 수 있습니다. (x - b) / c

하지만 이렇게 되면 소수점이 나오게 됩니다. 만약 나눠서 0 ~ 1 라면 부감독관은 한 명이 필요한 것이며, 1.xx ~ 2 라면 부감독관이 두명이 필요한 것입니다. 따라서 올림을 해주면 필요한 부감독관을 구할 수 있습니다.

따라서 math 모듈의 ceil() 함수를 이용하여 올림 처리를 해줍니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 알고리즘 백준 시험감독 파이썬

# 알고리즘 bj13458 python 시험감독

---