BOJ 10356 - Grammar

BOJ 10356 - Grammar

CYK 알고리즘 개념을 이용한 문제인데, 그냥 DP로 풀면 된다.

$dp[i][l][r]$ = $i(i \in N)$ 문자로 $x_l \sim x_r$ 구간의 문자열을 만들 수 있는지 여부

라고 둔다면

$O(26\lvert x \rvert^3)$ 에 문제가 해결되는데, 전처리를 해둬야 될 것도 있고 까다롭다.

시간초과나 메모리 초과를 조심해야한다.