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

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

[문제]

피보나치 수는 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은 1이상, 100000이하인 자연수입니다.

 

[코드]

class Solution {
  public int solution(int n) {
		int answer=0;
		
		/*
		 * n이 1과 2일때는 아래 if문으로 처리해줬기 때문에
		 * n이 3일 경우에 대한 초기화
		 * f(3) = f(1)+f(2) = 1+1 이므로
		 * num1과 num2를 1로 초기화한다. 
		 */
		int num1=1;
		int num2=1;
		
		if(n==1||n==2)
			return 1;
		else {
			for(int i=3;i<=n;i++) {
				answer=(num1+num2)%1234567;
				num1=num2; // 전전수로 갱신
				num2=answer; // 전수로 갱신
			}
		}
		return answer;
    }
}

 

[고찰]

 처음에는 재귀함수로 구현했는데 시간초과가 떠 반복문으로 구현하였다. 재귀함수는 같은 값을 여러번 반복 호출하기 때문에 메모리 사용량이 많아 시간초과가 뜬 것 같다. 따라서 재귀함수가 아닌 반복문 for를 사용하여 위와 같이 구현한다면 시간초과 없이 정답 처리를 받을 수 있다.