글 읽기 - 4206 반례/로직 질문

dahyun1226 3년 전 0

kmp를 사용했고, F를 20만보다 커졌을 때 10만씩 떼서 최대 20만으로 길이를 고정해놓고 풀었습니다.

dp는 그냥 dp[i] += kmp(F[i], bits) - dp[i - 1] - dp[i - 2]로 해결했습니다.

63퍼 정도에서 막혔습니다.

기본 테스트케이스나 확인해볼만한 애들은 통과했다고 생각합니다.

어떤 로직이 틀렸을까요?

# 백준 온라인 저지 4206반: 피보나치 단어

def makeFail(n: str):
    fail = [0] * len(n)
    matched = 0
    for index in range(1, len(n)):
        while n[matched] != n[index] and matched > 0:
            matched = fail[matched - 1]
        if n[matched] == n[index]:
            matched += 1
            fail[index] = matched
    return fail


def kmp(h: str, n: str):
    fail = makeFail(n)
    matched = 0
    result = []
    for index in range(0, len(h)):
        while matched > 0 and h[index] != n[matched]:
            matched = fail[matched - 1]
        if h[index] == n[matched]:
            matched += 1
            if matched == len(n):
                result.append(index - matched + 1)
                matched = fail[matched - 1]
    return len(result)


F = ["0"] * 101
F[1] = "1"
for i in range(1, 28):
    F[i + 1] = F[i] + F[i - 1]
    # 28 27은 20만 넘는다.
for i in range(29, 101):
    F[i] = F[i - 1][:100000] + F[i - 2][-100000:]

tc = 1
while True:
    try:
        dp = [0] * 101
        n = int(input())
        bits = input()
        if bits == '0': dp[0] = 1
        if bits == '1': dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
            if i <= 28:
                dp[i] += kmp(F[i], bits) - dp[i - 1] - dp[i - 2]
            elif i >= 29:
                dp[i] += kmp(F[i][-len(bits) + 1:] + F[i][:len(bits) - 1], bits)
        print("Case " + str(tc) + ": " + str(dp[n]))
        tc += 1
    except EOFError:
        break

nuclear852 3년 전 0

https://icpc.global/worldfinal...

2012 icpc worlds final에서 공개한 데이터셋이 있으니 확인하시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

4206 반례/로직 질문

dahyun1226 3년 전 0

nuclear852 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말