백준 10942 팰린드롬?

백준 10942 팰린드롬?

---

이번 문제는 DP 를 활용해야 하는 문제였는데, 분명 dp 란 것을 알고 있었음에도 어떻게 메모이제이션 해야할 지 감이 오지 않았고, 답을 참고해서 풀었다. 담에 이런 문제 나오면 무조건 스스로 해내야지!

i ~ j 까지의 범위가 팰린드롬인지 알기 위해선 i+1 ~ j-1 까지의 범위가 팰린드롬인지 부터 아는 것이 당연하다.


만약 i+1 ~ j-1 까지 팰린드롬이고 i 와 j 번째 의 수가 같다면, 당연 i~j 까지는 팰린드롬인 것이다.

이제 이 당연한 사실을 코드로 짜기만 하면 되는데, 그게 생각처럼 쉽지가 않다 하하하하

for (int i = 2; i <= n- 1; i++)
{
    for (int j =1 ; i +j <= n; j++)
    {
        if (numbers[j] == numbers[i+j] && dp[j+1][i+j-1] == 1)
        {
            dp[j][i+j] = 1;
        }
    }
}

이제 다 짰다 생각하고 제출했는데, 시간 초과가 나왔다. 혹시나 해서

ios_base::sync_with_stdio(0);
cin.tie(0);

깜빡하고 안 쓴 이 아이들을 써주니까 시간이 더 초과되지 않구 통과했다!!

아이디어를 떠올리는 거도 실패하고, 아이디어를 구현하는 것도 실패했다. 으악 담엔 더 잘하자