[코딩테스트 준비] 골드 1문제 (10942 펠린드롬?)

문제의 본질

• 수열 길이 N ≤ 2000
• 질문 개수 M ≤ 1,000,000

각 질문마다 직접 팰린드롬 검사하면 최악 O(N × M) → 절대 시간 안 됨

즉 모든 구간의 팰린드롬 여부를 미리 계산해야 한다.

 

핵심 아이디어: DP (Dynamic Programming)

정의

dp[i][j] = i번째 수부터 j번째 수까지가 팰린드롬이면 1, 아니면 0

 

점화식 

1️⃣ 길이 1

dp[i][i] = 1

• 한 글자는 무조건 팰린드롬

2️⃣ 길이 2

dp[i][i+1] = (arr[i] == arr[i+1])

 

3️⃣ 길이 ≥ 3

dp[i][j] = (arr[i] == arr[j]) AND dp[i+1][j-1]

• 양 끝이 같고
• 안쪽이 팰린드롬이면
• 전체도 팰린드롬

 

DP 채우는 순서 

구간 길이 기준으로 증가시키며 계산

길이 1 → 길이 2 → 길이 3 → ... → 길이 N

 

이유: dp[i][j]를 계산하려면 dp[i+1][j-1]가 이미 계산돼 있어야 함

 

시간 복잡도 분석

전처리

• DP 상태 수: N² ≈ 4,000,000
• 시간: O(N²) → 가능

질의

• 각 질문: O(1)
• 총: O(M)

전체 시간 O(N² + M) - 이 문제의 유일한 정답 접근