[BOJ] 15588번: Stamp Painting

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

좀 오랫동안 아이디어가 없어서 애를 먹었는데 갑자기 딱 떠올라서 풀어낼 수 있었습니다. 일단 문제를 잘 해석해보면 결국 어느 한 색이라도 k개 이상 연달아있으면 그 그림은 만들어낼 수 있으니 여집합, 즉 모든 색이 k번 연속해서 등장하지 않는 갯수를 구해봅시다. 그리고 $D[i]$를 i개의 캔버스가 있을 때 모든 색이 k번 연속해서 등장하지 않는 갯수라고 합시다. $D[i]$의 식을 찾는 것이 좀 까다로운데, $D[i]$에서 제일 끝의 색을 A라고 하고, A가 k개 연속해있다고 치면, 이는 $D[i-k]$에서 A로 끝나지 않는 모양들로부터 유도가 가능합니다. $D[i-k]$에서 A로 끝나지 않는 모양의 갯수는 $(M-1)/M * D[i-k]$이므로 최종적으로 식을 세워보면 $D[i] = (M-1)*(D[i-k+1]+D[i-k+2]+...+D[i-1])$이 됩니다. 이는 누적 합을 이용해 최종적으로 $O(N)$에 계산이 가능합니다.

https://github.com/blisstoner/BOJ/blob/master/15588.cpp