https://www.acmicpc.net/problem/30799
문제 요약
- 빨/주/노/초/파/남/보 순서가 s개 슬롯에 있어야함. 나머지는 슬롯은 알아서 채우고
- 경우의 수 구하기
접근법
- s개에서 7개를 고르고 나머지를 알아서 채우는 방식으로 하면 좋은데, 중복 제거가 힘듬
- 매 칸을 빨/주/노/초/파/남/보 로 채운다고 할때
- 이전 상태가 어느 색깔까지 연속으로 구성되었는지를 저장하고 있음 => dp
- 예를 들어 이전 상태가 파까지 연속으로 구성이 되었을 때(구성이 뭐가 되었건 어쨌든 파까지는 연속)
- 이번칸에 빨을 채우면 => 파까지 연속
- 주를 채우면 => 파까지 연속
- ....
- 남을 채우면 => 남까지 연속
- 보를 채우면 => 파까지 연속
- 모든 구성(0(아무것도 안됨) ~ 7(보))과 채울 색깔(1(빨) ~ 7(보))에 대해서 계산을 해보면
- 0 ~ 6은 다음번 1 ~ 7에 반영이 되고
- 0 ~ 6은 다음번에 각각 6번 쓰이고
- 7은 다음번에 7번 쓰임
newbieski