Algotithms [백준] 10941 팰린드롬? - 728x90 반응형 문제 홍준이가 자연수 N개를 칠판에 적고, 명우에게 질문을 M번 한다. 각 질문은 두 정수 S와 E로 나타낼 수 있고, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지 물어본다. 자연수 N개와 질문 M개가 모두 주어질 때, 명우의 대답을 구하는 프로그램 하기 1 <= N <= 2,0001 <= M <= 1,000,000 풀이 N이 최대 2000개 이므로 모든 팰린드롬의 경우의 수 ( Nx(N+1)//2 )를 구해두기로 하자. 팰린드롬은 gap이 0일 때와 1일 때를 미리 구해둔다. gap=0 ; 자기 자신이므로 항상 팰린드롬이다. gap=1 ; nums[i] == nums[i+1] 이면 팰린드롬이다. 반복문을 돌면서 gap=2 ~ N+1 까지의 값을 구한다. import sys input = sys.stdin.readline N = int(input()) nums = [0] + list(map(int, input().split())) # 팰린드롬 구하기 dp = [[0]*(N+1) for _ in range(N+1)] for i in range(1, N): dp[i][i] = 1 if nums[i] == nums[i+1] : dp[i][i+1] = 1 dp[N][N] = 1 for gap in range(2, N+1) : for s in range(1, N+1-gap) : if dp[s+1][s+gap-1] and nums[s] == nums[s+gap] : dp[s][s+gap] = 1 # 질문에 답변 for _ in range(int(input())) : S, E = map(int, input().split()) print(dp[S][E]) References 백준 DP 반응형 공유하기 URL 복사카카오톡 공유페이스북 공유엑스 공유 게시글 관리 구독하기Pino 저작자표시 비영리 변경금지 Contents 당신이 좋아할만한 콘텐츠 [백준] 5547 일루미네이션 2023.12.06 [백준] 20436 ZOAC 3 2023.12.06 [백준] 13164 행복 유치원 2023.12.05 [백준] 2668 숫자고르기 2023.11.02 댓글 1 + 이전 댓글 더보기