[BaekJoon Online Judge] 13458 – 시험 감독

문제

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

소스코드

총 감독관은 오직 1명만 있어야 하므로, 총 감독관 한 명이 감당할 수 있는 인원을 초과한 인원에 대해서 필요한 부감독관 수를 산정하면 되는데 if - else 만으로 구현하니 시간초과가 나서, elif 조건을 하나 더 추가해서, d[] 배열에 메모이제이션 한 결과를 리턴할 수 있도록 했다.

N = int(input())
A = list(map(int,input().split()))
B,C = map(int,input().split())

d = [0] * (max(A)+1)

cnt = 0
for i in range(N):
    if A[i]<=B:
        cnt += 1
        continue
    elif d[A[i]] != 0:
        cnt += d[A[i]]
    else:
        ref,tmp = B,1
        while A[i]>ref: tmp,ref = tmp+1,ref+C
        d[A[i]] = tmp
        cnt += tmp
print(cnt)