백준 1563. 개근상

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

1563번: 개근상

 

d[2][3][1001] // L 횟수, 마지막 연속 A 횟수, 날짜 

 

점화식을 하나하나 세심하게 세워야 하는 문제였다.

있을수 있는 조건은 다음과 같다.

 

[0][0][i] : L 없고, 마지막 연속되는 A 없음. ex) AAOO, AOAO ... 

[1][0][i] : L 하나 존재, 마지막 연속되는 A 없음. ex) OOOL, AAOL ... 

[0][1][i] : L 없고, 마지막 A 하나 존재. ex) AOOA, OAOA ... 

[1][1][i] : L 하나 존재, 마지막 A 하나 존재. ex) OOLA, AOLA ... 

[0][2][i] : L 없고, 마지막 연속되는 A 두개 존재. ex) OOAA, AOAA ... 

[1][2][i] : L 하나 존재, 마지막 연속되는 A 두개 존재. ex) OLAA, LOAA, ALAA ... 

 

[1][1][i] 와 [1][2][i] 가 마지막에 A 가 포함되는 것에 주의해야 한다.

예를들어 AAOO 같은건 A 가 두개 존재하지만 마지막에 있지 않기 때문에 [0][0][4] 에 해당한다.