[백준] #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공부는 해도해도 어렵다,,, 어떻게 문제를 쪼개는 지가 관건인데 많이 하다 보면 늘겠지,,, 화이팅
Author And Source
이 문제에 관하여([백준] #10942 Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@enchantee/백준-10942-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)