프로그래머스 피보나치 수

알고리즘

프로그래머스 피보나치 수

오래먹는오레오 2021. 1. 5. 09:34

피보나치 수 : 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) =

programmers.co.kr

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

이런 문장이 있다.

처음 나는 n번째 수만 1234567로 나눠 달라는 소린줄 알았는데 알고보니 모든 수를 1234567로 나누라는 소리였다.

class Solution {
  public int solution(int n) {
		int[] arr = new int[n + 1];
		arr[0] = 0;
		arr[1] = 1;
		for (int i = 2; i <= n; i++) {
			arr[i] = arr[i - 1] % 1234567 + arr[i - 2] % 1234567;
		}
		return arr[n]% 1234567;
	}
}