BOJ 10356 - Grammar
CYK 알고리즘 개념을 이용한 문제인데, 그냥 DP로 풀면 된다.
$dp[i][l][r]$ = $i(i \in N)$ 문자로 $x_l \sim x_r$ 구간의 문자열을 만들 수 있는지 여부
라고 둔다면
$O(26\lvert x \rvert^3)$ 에 문제가 해결되는데, 전처리를 해둬야 될 것도 있고 까다롭다.
시간초과나 메모리 초과를 조심해야한다.
CYK 알고리즘 개념을 이용한 문제인데, 그냥 DP로 풀면 된다.
$dp[i][l][r]$ = $i(i \in N)$ 문자로 $x_l \sim x_r$ 구간의 문자열을 만들 수 있는지 여부
라고 둔다면
$O(26\lvert x \rvert^3)$ 에 문제가 해결되는데, 전처리를 해둬야 될 것도 있고 까다롭다.
시간초과나 메모리 초과를 조심해야한다.
Comments