10942번 팰린드롬?

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

Keywords: Dynamic programming

10942번를 얼마전에 풀어서 그런지는 모르겠지만 아주 쉽게 풀었다. 점화식을 세울 때 “의존관계가 순환하는데..” 같은 고민을 1초 가량 했지만 10924번 처럼 대각선을 기준으로 위만 차례로 채운다고 생각하면 된다. 그리고, 이제는 이런 문제는 굳이 iterative DP로 끙끙대는 것보다는 recursive DP로 후루룩 풀고 놀러가는게 이득이라는 것도 안다.

그래도, 풀이를 안 적어놓을 수는 없으니까. 적어놓도록 한다.

Recursive DP solution 은 아래와 같다.

• CACHE[i][j] : i 번 숫자부터 j 번 숫자까지 회문을 이루는지의 여부
• CACHE[i][j] = CACHE[i+1][j-1] && NUMBERS[i+1] == NUMBERS[j-1]

솔루션은 여기 에서 확인할 수 있다.