글 읽기 - 이 코드에 대해서 반례를 제시해주거나 옳다는 것을 증명해주세요...(python)

kanght1219 2년 전 0

이 코드에 있는 어떤 특정한 반례만 고쳐서 풀으니 맞았습니다. 야매로 풀어서 맞는지 모르겠습니다...

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    st = list(sys.stdin.readline().rstrip("\n"))
    k = len(st)
    new = [["c", 0]]
    for i in range(k):
        if st[i] == new[-1][0]:
            new[-1][1] += 1
        else:
            new.append([st[i], 1])
    n = len(new) - 1
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(1, n - i + 1):
            if i == 0:
                dp[j][j + i] = (1 if new[j][1] > 1 else 0)
            elif i == 1:
                dp[j][j + i] = (1 if (new[j][1] > 1 and new[j + i][1] > 1) else 0)
            else:
                for q in range(j, j + i):
                    if dp[j][j + i]:  break
                    dp[j][j + i] = (1 if (dp[j][q] and dp[q + 1][j + i]) else 0)
                    if dp[j][j + i]: break
                    dp[j][j + i] = (1 if (dp[j][q] and dp[q + 1][j + i - 1] and new[j][0] == new[j + i][0]) else 0)
                    if dp[j][j + i]:  break
                    dp[j][j + i] = (1 if (dp[j][q] and dp[q + 1][j + i - 1] and new[j][0] == new[j + i][0]) else 0)
                if ((new[j][1] > 1 and new[j + i][1] > 1) or (new[j][0] == new[j + i][0])) and dp[j + 1][j + i - 1]:  dp[j][j + i] = 1
    print(dp[1][n])
#a/b3/a/b2/a

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

문제

문제

출처

ICPC

이 코드에 대해서 반례를 제시해주거나 옳다는 것을 증명해주세요...(python)

kanght1219 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말