프로그래머스 연습문제 - 피보나치 수 (level2)

프로그래머스 연습문제 - 피보나치 수(level2)

문제설명

제한사항 & 입출력 예

MySolution

def solution(n):
    answer = 0
    
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        answer += solution(n-2) + solution(n-1)
        return answer% 1234567

피보나치 수열은 대표적인 재귀함수의 예로 많이 사용해서 익숙한대로 재귀함수로 풀었더니 런타임 에러로 테스트 7~14까지 오답처리가 되었다

def solution(n):
  answer = []

  for i in range(0,n+1):
    if i == 0:
      answer.append(0)
    elif i==1 or i==2:
      answer.append(1)
    else:
      answer.append(answer[i-1]+answer[i-2])

  return answer[-1]%1234567

그래서 배열로 방향을 틀어서 답안을 수정했더니 통과되었다.

다른풀이

def fib(n):
    _curr, _next = 0, 1
    for _ in range(n):
        _curr, _next = _next, (_curr + _next) % 1234567 
    return _curr

자료형의 크기가 정해져있는 언어에서도 7~14번 테스트가 에러가 발생한다

한줄요약: 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다.
https://school.programmers.co.kr/questions/11969