Baekjoon 2560
in Study / Computer science on Baekjoon 2560
DP, Prefix Sum
Description
한 생물학자가 새로 발견된 짚신벌레 종의 생태에 대해 연구하고 있다. 매우 번식력이 강하다고 알려진 이 종은 아래와 같은 특징을 가지고 있다.
무성 생식을 한다.
- 태어난 이후 a일째 되는 날 성체가 된다.
- 성체가 된 날부터 매일 한 마리씩 새로운 개체를 만들어낸다: 성체가 되자마자 첫 개체를 만들어내고, 그 이후로 하루가 지날 때마다 새로운 개체를 하나씩 만들어낸다. 새로운 개체 역시 태어난 이후로 a일째 되는 날부터 성체가 되어 새로운 개체를 만든다.
- 태어난 이후로 b일째 되는 순간부터는 새로운 개체를 더 이상 만들지 않는다. 태어난 지 a일째 날부터 b일째 되는 날의 전날까지 새로운 개체를 만들어내므로 일생동안 총 b-a 마리의 개체를 만들어낸다.
- 태어난 이후로 d일째 되는 순간 죽는다.
아래는 a=2, b=4, d=6일 때 수조에 새로 태어난 짚신벌레 한 마리를 넣고 매일 관찰한 결과를 기록한 것이다. 괄호 안의 숫자들은 수조 안의 짚신벌레들이 각각 태어난 이후 며칠이 되었는지를 나타내는 정수이다.
- 태어난 날: (0) - 새로운 개체를 집어넣음
- 1일째 되는 날: (1) - 짚신벌레가 자람
- 2일째 되는 날: (2, 0) - 짚신벌레가 태어난 지 2일째가 되므로 성체가 되고 새 개체를 만들어 냄
- 3일째 되는 날: (3, 1, 0) - 2일째 성체가 된 짚신벌레가 오늘도 새 개체를 하나 만들어 냄
- 4일 째 되는 날: (4, 2, 1, 0) - 2일째 되는 날 만들어진 짚신벌레가 새로운 개체를 만들어 냄 (처음에 넣은 짚신벌레는 새 개체를 만들어내지 못함)
- 5일 째 되는 날: (5, 3, 2, 1, 0, 0)
- 6일 째 되는 날: (4, 3, 2, 1, 1, 0, 0) - 처음에 넣은 개체는 죽는다.
- 6일 째 되는 날 수조안에 살아있는 짚신벌레는 총 7마리가 된다.
짚신벌레의 번식 정보 a, b, d에 대하여, 새로 태어난 짚신벌레 한 마리를 수조 안에 넣은 이후 N일째 되는 날 살아있는 짚신벌레 수를 1000으로 나눈 나머지를 출력하는 프로그램을 작성하시오.
Input
첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다.
Output
첫째 줄에, 수조에 짚신벌레 한 마리를 넣은 지 N일째 되는 날 수조에 살아 있는 짚신벌레의 수를 1000으로 나눈 나머지를 출력한다.
Example I & O
Input 1
2 4 6 6
Output 1
7
Input 2
3 5 7 20000
Output 2
609
Input 3
10 24 31 61
Output 3
458
Input 4
1 3 4 1
Output 4
2
My solution
a, b, d, N = map(int, input().split())
dpForNum = [0] * (N + 1)
dpForNum[0] = 1
dpForBorn = [0] * (N + 1)
dpForBorn[0] = 1
sumL = [0] * (N + 1)
sumL[0] = 1
for i in range(1, N + 1):
if i >= a:
if i > b - 1:
dpForBorn[i] = (sumL[i - a] - sumL[i - b]) % 1000
else:
dpForBorn[i] = sumL[i - a] % 1000
if i >= d:
dpForNum[i] = (dpForNum[i - 1] + dpForBorn[i] - dpForBorn[i - d]) % 1000
else:
dpForNum[i] = (dpForNum[i - 1] + dpForBorn[i]) % 1000
sumL[i] = (sumL[i - 1] + dpForBorn[i]) % 1000
print(dpForNum[-1])
- Sketch
sum(dpForBorn[i - b + 1 : i - a + 1]) : inefficient → use Prefix Sum algorithm
- Code Analysis
a, b, d, N = map(int, input().split())
dpForNum = [0] * (N + 1)
dpForNum[0] = 1
dpForBorn = [0] * (N + 1)
dpForBorn[0] = 1
sumL = [0] * (N + 1)
sumL[0] = 1
a : start being reproducible
b : start being unreproducible
d : die
N : result of Day N
dpForNum : dp for total population
dpForBorn : dp for new born population
sumL : for prefix sum algorithm
for i in range(1, N + 1):
if i >= a:
if i > b - 1:
dpForBorn[i] = (sumL[i - a] - sumL[i - b]) % 1000
else:
dpForBorn[i] = sumL[i - a] % 1000
a <= i <= b - 1 : sum(dpForBorn[: i - a + 1])
i > b - 1 : sum(dpForBorn[i - b + 1 : i - a + 1])
if i >= d:
dpForNum[i] = (dpForNum[i - 1] + dpForBorn[i] - dpForBorn[i - d]) % 1000
else:
dpForNum[i] = (dpForNum[i - 1] + dpForBorn[i]) % 1000
Fill the value into dpForNum[i]
i < d : no dead population
i >= d : consider dead population
sumL[i] = (sumL[i - 1] + dpForBorn[i]) % 1000
By definition of sumL for prefix sum, sumL is filled simultaneously for efficiency
print(dpForNum[-1])
print the result