Algorithm/programmers
programmers 피보나치 수
wow
2022. 5. 1. 12:39
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) =
programmers.co.kr
문제 분석
- 피보나치 수의 정의대로 n번째 피보나치 수를 1234567로 나눈 나머지를 리턴한다.
- fibo라는 정수 배열을 활용하여 각 숫자에 해당하는 피보나치 수를 구한다. (이 때, 값을 그대로 저장하게되면 시간 초과가 나기때문에 배열에 값을 저장할 때 mod를 활용하여 1234567로 나눈 나머지의 값을 저장한다)
문제 풀이
1. for문을 통해 n번째 피보나치 수를 구한다.
2. 0, 1의 경우 이미 정의된 숫자를 할당한다.
3. 그 외의 경우 1234567로 나눈 나머지의 값을 배열에 저장한다.
4. 해당 숫자에 해당하는 피보나치 수를 리턴한다.
class Solution {
public int solution(int n) {
int answer = 0;
int fibo[] = new int[n+1];
for(int i=0;i<n+1;i++){
if(i==0){
fibo[i] = 0;
}else if(i==1){
fibo[i] = 1;
}else{
fibo[i] = (fibo[i-1]+fibo[i-2])%1234567;
}
}
answer = fibo[n];
return answer;
}
}