[Python] BOJ(백준) 10942번 - 팰린드롬?

링크

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

난이도(solved.ac 참고)

골드3

풀이

질문의 수가 100만개까지 있을 수 있기 때문에 인덱싱을 하면 100% 틀린다.

특정 구간이 팰린드롬이기 위해서는 3가지 조건 중 하나를 만족해야 한다.

1) 구간의 길이가 1이어야 한다.

- 구간의 길이가 1이라면 무조건 팰린드롬이다.

2) 구간의 길이가 2라면 두 값이 같아야 한다.

- 숫자가 두개가 있을 땐 무조건 같을 경우에만 팰린드롬이 되며, 다르다면 팰린드롬의 조건을 만족하지 못한다.

3) 구간의 길이가 3 이상이라면, 구간의 시작점과 끝점의 값이 같으면서 그 두 점을 제외한 구간이 팰린드롬이어야 한다.

- 1 2 1 3 1 2 1 에서 1 3 1 2 1을 떼서 봤다고 해보자. 이 경우 시작점과 끝점이 모두 1이지만 이 두개를 제외한 3 1 2는 팰린드롬의 조건을 만족하지 못하므로 팰린드롬이 아니다.

 

이 세 가지를 알았다면(즉 DP를 사용해서 두 점을 제외한 구간의 값을 사용해야 한다는 것을 알았다면), 구현은 풀이처럼 하면 된다.