피보나치 수
문제정의
피보나치의 n번째 수열을 1234567로 나눈 나머지 값을 구하는 문제이다.
문제풀이
전체 코드는 다음과 같다. 숫자가 자칫 커질꺼라 long을 쓸 수도 있는데 나머지 연산은 분배법칙이 통한다는 것을 알면 문제가 쉽게 풀린다. 일반적인 피보나치 수를 구하는 공식에 나머지 연산만 취해주면 된다.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22package level2;
public class Fibonacci {
//프로그래머스 문제풀이 level2 피보나치 수
public static void main(String[] args) {
int n = 5;
int a = 0, b = 1, c = 0;
for(int i = 2; i <= n; i++)
{
a %= 1234567;
b %= 1234567;
c = a+b;
a = b;
b = c;
c %= 1234567;
}
System.out.println(c);
}
}
시간복잡도는 \(O(n)\)이다.
테스트
