[백준 / BOJ] 2560 짚신벌레

문제

출처 : https://www.acmicpc.net/problem/2560

2560번: 짚신벌레

한 생물학자가 새로 발견된 짚신벌레에 대해 연구하고있다.

짚신벌레는

1. 태어난지 a일째 되는날부터 새로운 개체를 생성한다.

2. 태어난지 b일째 되는날부터 새로운 개체생성을 중지한다(a일부터 b-1일 까지 개체를 생성함)

3. 태어난지 d일째 되는날 죽는다.

 

수조안에 짚신벌레가 한마리 있다할때, N일 지난후 살아있는 짚신벌레 개체수를 구하는 문제다.

 

 

풀이

완전탐색으로 풀경우, d*d*N = O(N*(d^2))이 되어서 시간초과가 나온다. 다이나믹 프로그래밍으로 풀어야하는 문제였다.

 

우리가 알아야할 정보는 N일 째 되는날에 살아있는 짚신벌레의 개체 수이다.

즉, 짚신벌레의 총 개체수가 중요한거지, 각각의 짚신벌레가 몇일을 살았나 알필요는 없다.

 

day만큼 날이 지났을때, 살아있는 짚신벌레의 수를 다음과 같이 표현한다고 하자.

 

ins[day] = 짚신벌레의 수

 

짚신벌레가 a일 부터 새로운 개체를 생성하니, day-a일에 있는 모든 짚신벌레는 a일이 지난후 새로운 개체를 생성하기 시작할것이다.

day-1에 생존해있던 짚신벌레는 그대로 생존해있는상태로 다음날로 올것이다.

따라서, day날 새롭게 추가되는 짚신벌레의 총 개체수는 ins[day] = ins[day-1] + ins[day-a] 가 된다.

 

이때, 짚신벌레가 b일이 지난후 더 이상 개체를 생성하지 못하는 경우를 고려해줘야한다.

이 경우도 마찬가지로 짚신벌레는 b일부터 새로운 개체를 생성하지못하니, day-b일에 있는 모든 짚신벌레는 b일이 지난후 새로운 개체를 생성하지 못한다. 

 

위에 두 경우를 합치면, 짚신벌레의 총 개체수를 찾는 최종 점화식은

ins[day] = ins[day-1]+ins[day-a]-ins[day-b] 가 된다. (day-a >= 0 && day-b >= 0)

 

N일째 된날에 죽은 짚신벌레의 수는, 

짚신벌레는 d일살면 죽으니, N일부터 d일전에 살아있던 짚신벌레는 모두 죽는다. 

따라서, N일째에 죽는 짚신벌레의 수는 ins[N-d] 와 같이 구할수있다.

 

따라서, N일에 짚신벌레의 총 개체수에 N일에 죽는 짚신벌레의 개체수를 빼주면 (ins[N]-ins[N-d])된다.

 

모듈러 연산을 사용할때 주의해야했다.

점화식에 뺄셈이 들어가있으므로, 모듈러 연산중 값이 음수가 될수있기 때문에

(a-b)%mod = ((a%mod) -( b%mod) + mod) % mod 와 같이 mod값을 더해주며 값이 음수로 변하는것을 방지해줘야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2560%20%EC%A7%9A%EC%8B%A0%EB%B2%8C%EB%A0%88/main.cpp

devxb/JJUNalgo