백준 12199 - Password Attacker (Large)

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

문제의 조건을 만족하는 비밀번호의 갯수를 구하기 위해 다음 점화식을 고려할 수 있다.

dp(i, j) := 입력할 수 있는 문자가 i개 남았고 아직 쓰지 않은 키가 j개 남았을 때 최적해

문제에서 j개의 키를 반드시 사용하라고 했으므로 j가 0이 되는 방법을 동적 계획법으로 계산하면 문제의 정답을 구할 수 있다.