로다 - COCI_2016C2_SAVEZ

문제 링크(koitp.org/problem/COCI_2016C2_SAVEZ/)

해싱을 이용한 동적계획법으로 해결할 수 있다.

D(i, p, q) : i번째 문자열까지 고려했을 때, prefix 해시값이 p, suffix 해시값이 q일 때의 최대 텔레포트 횟수

i번째 문자열의 prefix와 suffix들에 대해 D(i-1)의 값으로 D(i, p, q)값을 갱신하면 된다.

그런데 여기서 첫번째 차원인 i는 (p, q)가 누적되는 성질에 따라 불필요하게 된다.