글 읽기 - 2079번 팰린드롬 반례를 못찾겠습니다 (파이썬)

iknoom1107 5년 전 1

i <- 0 to N

j <- 0 to i-1 순서로

j부터 i까지 팰린드롬이고 dp[j-1]+1이 dp[i]보다 작으면 dp[i]를 갱신합니다

예제들은 모두 잘 나오고 다양하게 입력해봤습니다
그런데 입력하면 바로 틀렸습니다가 뜹니다
어디가 잘못된건지 모르겠습니다....

부탁드립니다

import sys
input=sys.stdin.readline
n=input()
N=len(n)

dp=[[False]*N for _ in range(N)]
for i in range(N):dp[i][i]=True
for i in range(N-1):
	if n[i]==n[i+1]:dp[i][i+1]=True
	else:dp[i][i+1]=False

for k in range(2,N+1):
	for i in range(N-k):
		j=i+k
		if dp[i+1][j-1] and n[i]==n[j]:dp[i][j]=True
		else:dp[i][j]=False

dp2=[0]*N
dp2[0]=1
for i in range(1,N):
	dp2[i]=dp2[i-1]+1
	for j in range(i-1):
		if n[j]==n[i] and dp[j+1][i-1]:
			if j==0:dp2[i]=1
			else:dp2[i]=min(dp2[i],dp2[j-1]+1)
	if n[i-1]==n[i]:
		if i==1:dp2[i]=1
		else:dp2[i]=min(dp2[i],dp2[i-2]+1)

print(dp2[-1])

nova9128 5년 전 1

입력시 sys.stdin.readline() 사용하시면 개행문자도 문자로 인식하게 됩니다.

뒤에 sys.stdin.readline().strip() 넣어주셔야합니다.

아니면 애초에 strip() 효과가 있는 input() 으로 입력받으면 됩니다.

nova9128 5년 전 0

https://www.acmicpc.net/board/...

불규칙적인 개행문자가 입력데이터에 있는것같아서 수정요청하였습니다.

iknoom1107 5년 전 0

덕분에 해결됐습니다

정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2079번 팰린드롬 반례를 못찾겠습니다 (파이썬)

iknoom1107 5년 전 1

nova9128 5년 전 1

nova9128 5년 전 0

iknoom1107 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말