글 읽기 - 틀린 풀이일까요?

caffeinism7 5년 전 0

피보나치에서 loop가 생기는 부분을 찾아 입력된 n이 그 루프의 어느 부분인지 찾아서 출력하도록 했습니다. 잘못된 풀이일까요? 아니면 코드에 뭔가 문제가 있을까요?

n = int(input())
dic = {}
a, b = 0, 1
for i in range(2, 1000000000000):
    f = (a + b) % 1000000
    if f in dic:
        loop_start = dic[f]
        break;
    dic[f] = i
    a, b = b, a + b

dic = {v: k for k, v in dic.items()}
dic[0] = 0
dic[1] = 1
if n < len(dic):
    print(dic[n])
else:
    n = (n - len(dic)) % (len(dic) - loop_start) + loop_start
    print(dic[n])

jh05013 5년 전 1

값이 같은 항이라도 이전 항이 다르면 다음 항도 다릅니다. 예를 들어 10으로 나눈 나머지를 생각해 보면, 1 2 3 5 8 3이 되어 세 번째와 여섯 번째가 같지만, 그 다음 수는 5가 아니라 1입니다.

caffeinism7 5년 전 0

아하 그렇군요 감사합니다.

caffeinism7 5년 전 0

왠지 짧은 루프가 나오더라고요 다른 방법을 찾아봐야겠네요.

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

문제

문제

출처

ICPC

틀린 풀이일까요?

caffeinism7 5년 전 0

jh05013 5년 전 1

caffeinism7 5년 전 0

caffeinism7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말