[프로그래머스] 피보나치 수

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

제출 답안

탑다운

• 함수 밖에 d를 선언했다.
  • 100,001로 한 이유는 n이 최대 100,000이기에 그렇다.
• 만약 1 또는 2가 들어오면 1을 리턴한다.
• 그리고 이미 계산한 적이 있다면 해당 인덱스의 값을 리턴한다.
• 계산한 적이 없는 인덱스는 재귀로 계산된 값으로 업데이트 한다.
• 마지막에 1234567로 나눈다.
• 근데 이 방법은 런타임 오류가 발생하여 보텀업으로 제출해야 통과하였다.

d = [0] * 100001
def solution(n):
    if n == 1 or n == 2:
        return 1
    if d[n] != 0:
        return d[n]
    d[n] = solution(n - 1) + solution(n - 2)
    return d[n] % 1234567

테스트 1 〉	통과 (0.01ms, 10.5MB)
테스트 2 〉	통과 (0.01ms, 10.6MB)
테스트 3 〉	통과 (0.01ms, 10.4MB)
테스트 4 〉	통과 (0.01ms, 10.4MB)
테스트 5 〉	통과 (0.01ms, 10.6MB)
테스트 6 〉	통과 (0.01ms, 10.4MB)
테스트 7 〉	실패 (런타임 에러)
테스트 8 〉	통과 (1.11ms, 11.5MB)
테스트 9 〉	통과 (0.24ms, 10.9MB)
테스트 10 〉	실패 (런타임 에러)
테스트 11 〉	통과 (0.63ms, 11.1MB)
테스트 12 〉	통과 (0.82ms, 10.9MB)
테스트 13 〉	실패 (런타임 에러)
테스트 14 〉	실패 (런타임 에러)

보텀업

• 모든 값이 0인 리스트를 생성한다.
• 그리고 1과 2는 미리 계산하여 결과를 업데이트 한다.
• 3부터는 계산이 가능하니 for loop로 계산한다.
• n번째 수를 나눠 나머지를 return한다.

def solution(n):
    d = [0] * (n + 1)
    d[1] = 1
    d[2] = 1
    for i in range(3, n + 1):
        d[i] = d[i - 1] + d[i - 2]
    answer = d[n] % 1234567
    return answer

테스트 1 〉	통과 (0.00ms, 10.2MB)
테스트 2 〉	통과 (0.00ms, 10.1MB)
테스트 3 〉	통과 (0.00ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	통과 (0.30ms, 10.2MB)
테스트 8 〉	통과 (0.15ms, 10.1MB)
테스트 9 〉	통과 (0.05ms, 10.2MB)
테스트 10 〉	통과 (0.35ms, 10.1MB)
테스트 11 〉	통과 (0.07ms, 10.2MB)
테스트 12 〉	통과 (0.18ms, 10.1MB)
테스트 13 〉	통과 (488.80ms, 456MB)
테스트 14 〉	통과 (429.53ms, 439MB)