13458 - 시험 감독

 

---

 

문제

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

13458번: 시험 감독

 

풀이

dp로 풀었다.

 

우선 총 감독관이 커버할 수 있는 경우는 모두 1명으로 초기화 했고,

 

이후에 +c명까지 부감독관 한명씩 늘려주면 된다.

 

범위 체크만 잘해서 입력값의 한계까지 구한다음, dp배열에 접근하여 값만 더해주면 된다.

 

코드

from sys import stdin

n = int(input())
a = list(map(int, stdin.readline().rstrip().split()))
b, c = map(int, input().split())

# 초기화
d = [-1] * 1000001
person = 1

# 총 감독관 한명으로 커버 가능할때까지
while True:
    if person <= b:
        d[person] = 1
    else:
        break
    person +=1

# person ~ person+b 명까지는 부감독이 1명 추가로 필요하다.
while True:
    val = d[person - 1]
    if person+c > 1000000:
        for i in range(person, 1000001):
            d[i] = val+1
        break
    for i in range(person, person+c):
        d[i] = val+1
    person += c

answer = 0
for val in a:
    answer += d[val]
print(answer)

 

후기

 

입력값이 큰 친구들은 dp의심 !