100번할 것을 1번만에 하는 나눗셈 연산 -시험 감독-

1. 문제

 

13458번: 시험 감독 (acmicpc.net)

13458번: 시험 감독

 

각 시험장의 응시자 수가 주어지고, 총 감독관은 b명, 부 감독관은 c명만큼 감시가 가능하다.

 

모든 시험장의 응시자들을 감시할 수 있는 필요한 감독관의 최솟값을 구하는 프로그램을 작성

 

 

2. 풀이

 

문제 설명이 아쉽긴한데 총 감독관은 필수로 1명을 배치해야하고, 부 감독관은 0명 이상을 배치해야한다

 

총 감독관 1명을 배치하면, b명을 감시할 수 있으니까, 감시해야할 응시자 수는 s-b이다

 

최초에는 빼기 연산을 반복해서... 했었는데

 

from sys import stdin

n = int(stdin.readline())

student_list = list(map(int,stdin.readline().split()))

b,c = map(int,stdin.readline().split())

ans = 0

for s in student_list:
    
    #총 감독관
    ans += 1

    s -= b

    while s > 0:
        
        ans += 1

        s -= c
    
print(ans)

 

응시자 수가 100만까지 가능하다보니까 시간초과

 

근데 계속 빼기해서 1씩 더해주면... 언제까지 더해주는지 생각을 해보면

 

s = ck가 될때, ans에 k를 더해주는건데..이 k는 s를 c로 나눈 몫이 된다

 

그러니까 나눗셈 단 1번으로 k번 빼기하는 것과 동일하다

 

.. 나눗셈 1번만 해서 몫만큼 더해주는거랑 연산상으로 당연히 나눗셈 1번이 이득이다

 

이 테크닉을 사용했던 문제가 개미 문제였던가?

 

아무튼 나눗셈.. 적극적으로 생각하자

 

from sys import stdin

#시험장 수
n = int(stdin.readline())

#응시자 수
student_list = list(map(int,stdin.readline().split()))

#총감독관, 부감독관 감시 수
b,c = map(int,stdin.readline().split())

ans = 0

#응시자 수를 순회해서,
for s in student_list:
    
    #총 감독관 1명을 필수로 배치하고
    ans += 1
        
    s -= b
    
    #1명을 배치하더라도, 응시자 수가 남아있다면,
    if s > 0:
        
        #남은 응시자 수를 부감독관이 감시할 수 있는 수로 나눠줘서,
        k,r = divmod(s,c)
        
        #나머지가 양수라면, 부감독관 1명을 더 배치하고
        if r > 0:
            
            ans += (k+1)
        
        #나머지가 0이라면 몫만큼 배치하면 된다
        else:
            
            ans += k

print(ans)