[일반] 이문제 질문좀.. 힌트라도 ㅠㅠ

[익명(210.219)]

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

시간제한을 보니 팰린드롬을 다 구해놓고

요청올때마다 찍어줘야될거같은데

어떻게 해야할까용...

- dc official App

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(210.219)]

분류가dp인댕.. - dc App

[뉴비(220.92)]

죄송합ㄴ디ㅏ

[뉴비(220.92)]

이걸아 비슷한거 푼적있어서 ㅜㅜㅜㅜㅜ그건줄알았어요

[익명(61.72)]

질문자님이 말한대로 해도될거같은데요

[익명(210.219)]

어떻게가 잘 안되네요.. 모든 구간을 일일히 구하면 너무 오래걸릴것같은데 - dc App

[익명(58.77)]

Manacher’s algorithm 구글링 ㄱ

[익명(58.77)]

제한을 보니 매니처까진 필요없고 N^2 DP를 생각해보셈

[익명(210.219)]

고민해볼게요 - dc App

[익명(61.72)]

pal[i]=자리 i를 중심으로 가장 긴 팰린드롬의 길이. 이렇게한다면 이 pal을 구하는데 단순하게 하면 O(n^2)만에 가능하겠죠? 그리고 각 쿼리마다 바로바로 답을 구할수있는데 어느부분이 오래걸린다고 생각하시는지용

[익명(210.219)]

답변해주신 선생님들 감사합니다 풀고 보니까 모두 좋은 조언이었네요 - dc App

[익명(61.72)]

윗분말씀대로 Manacher를 사용하면 O(n)만에 가능하긴한데 O(n^2)방법이라면 DP가아니라 단순 팰린드롬인지 확인하는방법으로 구할수있어요.

[익명(218.54)]

i..j 구간이 팰린드롬이면 i+1..j-1 구간도 팰린드롬

[익명(218.54)]

D[i][j] = i..j 구간이 팰린드롬인지 여부 = D[i+1][j-1] && A[i]==A[j]

[익명(210.219)]

정말 좋은 조언 감사합니다 풀었습니다 - dc App