[백준] #10942 Python

백준 10942번 파이썬
https://www.acmicpc.net/problem/10942

아이디어

DP 문제이다. 큰 문제를 어떻게 작은 문제로 나누는지가 관건인데, 전형적인 Knansack 문제나 1로 만들기 문제와 같이 직관적으로 나누는 방법이 보이진 않는다. 결국은 팰린드롬이기 때문에 현재 보고자 하는 '시작~끝'의 수열을 확인하려면 '시작+1~끝-1'의 수열을 확인해야 한다.

DP[시작][끝]의 형태로 만들고 해당 위치의 값은 0과 1.
다른 DP 문제와 살짝 다른 점은 DP의 2차원 배열을 시작과 끝의 관점으로 도는 것이 아니라, b라는 변수를 추가해 시작과 차이(끝-시작)의 관점으로 돈다는 점이다. 따라서 Bottom-Top 방식으로 차이가 0인 수열, 차이가 1이지만 시작과 끝의 숫자가 같은 수열부터 팰린드롬 여부를 정할 수 있다.

전체코드

import sys
input = sys.stdin.readline

N = int(input())
L = [0] + list(map(int, input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]

for b in range(N): # 차이가 0, 1인 것부터 먼저 채워야 됨 -> dp 도는 기준: 차이, start
    for start in range(1, N+1):
        end = start + b

        if end > N:
            break
        if b == 0:
            dp[start][end] = 1
        elif b == 1 and L[end] == L[start]:
            dp[start][end] = 1
        elif L[start] == L[end] and dp[start + 1][end -1] == 1:
            dp[start][end] = 1
        else:
            dp[start][end] = 0
        

M = int(input())
for i in range(M):
    a, b = map(int, input().split())
    print(dp[a][b])

느낀점

DP공부는 해도해도 어렵다,,, 어떻게 문제를 쪼개는 지가 관건인데 많이 하다 보면 늘겠지,,, 화이팅