백준 1563. 개근상

tose33 2023. 10. 11. 14:04

1563번: 개근상

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독

www.acmicpc.net

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] 에 해당한다.