[백준] 10942번 팰린드롬?
8597 단어 다이나믹 프로그래밍다이나믹 프로그래밍
문제 링크
https://www.acmicpc.net/problem/10942
문제 설명
- 2000개 숫자가 주어짐
- 100만개 start, end 인덱스가 주어짐
- start ~ end 가 팰린드롬이면 1, 아니면 0 출력
풀이
-
dp 배열을 놓는다
-
dp[s][e] : s~e가 팰린드롬이면 1, 아니면 0
-
양 끝이 같고 사이가 팰린드롬이면 1
-
bottom-up으로 순회
- 즉, 사이가 bottom
-
숫자가 2000개라 O(N^2) 가능
파이썬 코드
import sys
def solution():
# 입력 받기
read = sys.stdin.readline
write = sys.stdout.write
n = int(read())
numbers = list(map(int, read().split()))
m = int(read())
questions = [list(map(int, read().split())) for _ in range(m)]
# dp[i][j] s=i, e=j 일때 팰린드롬이면 1, 아니면 0
dp = [[0]*n for _ in range(n)]
# 길이가 1일 때
for i in range(n):
dp[i][i] = 1
# 길이가 2일 때
for i in range(n-1):
if numbers[i] == numbers[i+1]:
dp[i][i+1] = 1
# 나머지
num = 2
while True:
s, e = 0, num
while True:
# 양끝이 같고 사이가 팰린드롬이면
if numbers[s] == numbers[e] and dp[s+1][e-1] == 1:
dp[s][e] = 1
s += 1
e += 1
if e == n:
break
num += 1
if num == n:
break
# 프린트
# for line in dp: print(line)
for s, e in questions:
write(f'{dp[s-1][e-1]}\n')
solution()
Author And Source
이 문제에 관하여([백준] 10942번 팰린드롬?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-10942번-팰린드롬
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
-
dp 배열을 놓는다
-
dp[s][e] : s~e가 팰린드롬이면 1, 아니면 0
-
양 끝이 같고 사이가 팰린드롬이면 1
-
bottom-up으로 순회
- 즉, 사이가 bottom
-
숫자가 2000개라 O(N^2) 가능
파이썬 코드
import sys
def solution():
# 입력 받기
read = sys.stdin.readline
write = sys.stdout.write
n = int(read())
numbers = list(map(int, read().split()))
m = int(read())
questions = [list(map(int, read().split())) for _ in range(m)]
# dp[i][j] s=i, e=j 일때 팰린드롬이면 1, 아니면 0
dp = [[0]*n for _ in range(n)]
# 길이가 1일 때
for i in range(n):
dp[i][i] = 1
# 길이가 2일 때
for i in range(n-1):
if numbers[i] == numbers[i+1]:
dp[i][i+1] = 1
# 나머지
num = 2
while True:
s, e = 0, num
while True:
# 양끝이 같고 사이가 팰린드롬이면
if numbers[s] == numbers[e] and dp[s+1][e-1] == 1:
dp[s][e] = 1
s += 1
e += 1
if e == n:
break
num += 1
if num == n:
break
# 프린트
# for line in dp: print(line)
for s, e in questions:
write(f'{dp[s-1][e-1]}\n')
solution()
Author And Source
이 문제에 관하여([백준] 10942번 팰린드롬?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-10942번-팰린드롬
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
def solution():
# 입력 받기
read = sys.stdin.readline
write = sys.stdout.write
n = int(read())
numbers = list(map(int, read().split()))
m = int(read())
questions = [list(map(int, read().split())) for _ in range(m)]
# dp[i][j] s=i, e=j 일때 팰린드롬이면 1, 아니면 0
dp = [[0]*n for _ in range(n)]
# 길이가 1일 때
for i in range(n):
dp[i][i] = 1
# 길이가 2일 때
for i in range(n-1):
if numbers[i] == numbers[i+1]:
dp[i][i+1] = 1
# 나머지
num = 2
while True:
s, e = 0, num
while True:
# 양끝이 같고 사이가 팰린드롬이면
if numbers[s] == numbers[e] and dp[s+1][e-1] == 1:
dp[s][e] = 1
s += 1
e += 1
if e == n:
break
num += 1
if num == n:
break
# 프린트
# for line in dp: print(line)
for s, e in questions:
write(f'{dp[s-1][e-1]}\n')
solution()
Author And Source
이 문제에 관하여([백준] 10942번 팰린드롬?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-10942번-팰린드롬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)