[일반] ㅅㅂ 이거 왤케 일차원 dp로 풀릴거 같지

[익명(223.38)]

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

전처리 좀 하면 일차원으로 풀릴거 같은데

골 1인데 일차원으로 풀리는게 이상해서 그럼

걍 내 착각인가?

- dc official App

[익명(49.168)]

n^2 밖에 안 보이는데 어케함

[익명(223.38)]

전처리가 N^2임 - dc App

[익명(221.163)]

애초에 펠린드롬 여부를 저장하려면 이차원이 편하잖아

[익명(223.38)]

그런가 난 일차원밖에 생각이 안났음

[익명(223.38)]

되는구나 착각이 아니였네
http://boj.kr/c9c50a05b56d4446a6672fb81b1f8db4

[익명(49.168)]

dp 상태수가 O(N)이고 상태 전이가 O(N)인거지

[익명(223.38)]

아 난 배열이 일차원인거 말한거였는데 그냥 시간복잡도가 N^2이면 그것도 이차원 DP라 하나보네 - dc App