2560. 짚신벌레

2560번: 짚신벌레

---

규칙에 따라 변하는 짚신벌레의 상태를 추적하는 문제이다. 딱 봐도 dp스럽지 않은가? 짚신벌레의 상태는 날짜에 의해서만 변하므로, $i$번째 날의 값을 알면 $i+1$번째 날의 값도 알 수 있다.

 

다음을 정의한다.

 

$t[i][j]$: $i$번째 날에 상태가 $j$로 바뀌는 짚신벌레의 수

$sum[i][j]$: $i$번째 날에 상태가 $j$인 짚신벌레의 수 ($t$의 부분합이라고 생각하면 좋다)

 

상태 $j$는 다음과 같다.

• $j = 0$: 태어남 (태어났지만 성체는 아님)
• $j = 1$: 성체가 됨 (번식 중)
• $j = 2$: 번식을 중단함

$j = 1$

문제에서 짚신벌레는 성체가 되자마자 번식한다고 했다. 따라서 $j = 0$보다 $j = 1$을 먼저 계산해야 한다.

• $i$번째 날에 성체가 되는 짚신벌레는 $i-a$일 전에 태어난 짚신벌레이다. 따라서 $t[i][1] = t[i-a][0]$이다.
• $i$번째 날에 성체인 짚신벌레의 수는 $i-1$번째 날에 성체였던 짚신벌레의 수에서 번식을 중단한 짚신벌레의 수를 빼고, 새로 성체가 된 짚신벌레의 수를 더하면 된다. $i$번째에 번식을 중단하는 짚신벌레는 $b$일 전에 태어난 짚신벌레이다. 따라서 $sum[i][1] = sum[i-1][1] - t[i-b][0] + t[i][1]$이다.

$j = 0$

• $i$번째 날에 태어난 짚신벌레의 수는 $i$번째 날에 성체인 짚신벌레의 수와 같다. 따라서 $t[i][0] = sum[i][1]$이다.
• $i$번째 날의 어린(아직 번식하지 못하는) 짚신벌레의 수는 $i-1$번째 날의 어린 짚신벌레의 수에서 성체가 된 짚신벌레의 수를 빼고, 새로 태어난 수를 더하면 된다. $i$번째 날에 성체가 되는 짚신벌레는 $a$일 전에 태어난 짚신벌레이다. 따라서 $sum[i][0] = sum[i-1][0] - t[i-a][0] + t[i][0]$이다.

$j = 2$

• $i$번째 날에 처음 번식을 중단하는 짚신벌레는 $i-b$번째 날에 태어난 짚신벌레이다. 따라서 $t[i][2] = t[i-b][0]$이다.
• $i$번째 날에 번식을 중단하고 있는 짚신벌레는 $i-1$번째 날에 번식을 중단하고 있던 짚신벌레의 수에서 $i$번째 날에 죽은 짚신벌레의 수를 빼고, $i$번째 날에 처음 번식을 중단한 짚신벌레의 수를 더하면 된다. $i$번째 날에 죽는 짚신벌레는 $i-d$일에 태어난 짚신벌레이다. 따라서 $sum[i][2] = sum[i-1][2] - t[i-d][0] + t[i][2]$이다.

주의

나머지 연산에 주의하자. 나머지를 취하기 전에 1000을 더해야 한다. 나머지와 실제 값의 대소관계는 다를 수 있기 때문이다.

---

간만에 글 쓰기 좋은 문제를 풀었다.