새소식

반응형
Algotithms

[백준] 10941 팰린드롬?

  • -
728x90
반응형

문제

  • 홍준이가 자연수 N개를 칠판에 적고, 명우에게 질문을 M번 한다.
  • 각 질문은 두 정수 S와 E로 나타낼 수 있고, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지 물어본다.
  • 자연수 N개와 질문 M개가 모두 주어질 때, 명우의 대답을 구하는 프로그램 하기

 

  • 1 <= N <= 2,000
    1 <= 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
반응형
Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.