백준 10942 팰린드롬? 문제 풀이
백준 10942 팰린드롬? 문제 풀이
백준 온라인 저지, 10942번: 팰린드롬?
도입
이 문제는 매우 빡빡한 시간 조건과 매우 넓은 범위의 입력값을 가졌다.
언듯 보면 팰린드롬 여부만 파악하면 될 것 같지만, 1십만 개의 숫자 배열에 대해 최대 1백만회 일정 범위에 대해 팰린드롬에 대해 물어볼 수 있다.
팰린드롬 처리에만 집중한다면 시간 초과가 발생하기 쉽다.
문제 풀어보기
1백만회에 이르는 쿼리들이 요구하는 부분 수열의 범위는 서로 부분적으로 겹칠 가능성이 매우 높다.
따라서 쿼리 중 부분 수열의 팰린드롬 확인 결과만 저장하더라도 반복되는 부분 수열 쿼리를 획기적으로 생략할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def is_pal(self, init: int, fin: int) -> bool:
...
if fin - init > 1:
pal = self.is_pal(init + 1, fin - 1)
if not pal:
self.dp[init][fin] = False
else:
if nums[init] == nums[fin]:
self.dp[init][fin] = True
else:
self.dp[init][fin] = False
else:
if nums[init] == nums[fin]:
self.dp[init][fin] = True
else:
self.dp[init][fin] = False
...