https://www.acmicpc.net/problem/2748
문제
> 피보나치 수는 0과 1로 시작한다.
> 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
> 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
> 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
> n=17일때 까지 피보나치 수를 써보면 다음과 같다.
> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
> n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.접근
피보나치 수열을 구하고 주어진 n에 대해 뽑아서 출력한다.
문제해결
> 문제의 범위인 0부터 90까지 사용하기 위해 배열의 크기를 91로 만들어 준다.
> 0과 1에 대해 미리 초기값을 넣어주고 피보나치 수열 공식을 사용해 구해준다.
> 90번 째 까지 i-1과 i-2의 합으로 전부 구해준 뒤 입력받은 n번째 값을 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//2748번 피보나치 수 2
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[] fiv = new long[91];
fiv[0] = 0;
fiv[1] = 1;
for(int i = 2; i < fiv.length; i++) fiv[i] = fiv[i-2]+fiv[i-1];
System.out.print(fiv[n]);
}
}
후기
처음에 틀렸다길래 틀릴만한 곳이 int형 밖에 없었다. 그래서 90을 넣어 찍어봤더니 쓰레기값이나왔고, long형으로 바꿔주니 맞았다. 피보나치 수는 47이 되면 3x1e9로 int형으로 담을 수 있는 최대값을 넘어간다고 한다.
하지만 배열을 사용하지 않고 a,b로 초기값을 각각 0,1로 준뒤
i는 2부터 반복문으로 n까지 c = a+b, a = b, b = c로 구해줄 수 있다고 한다. 이 생각은 못해봤다. 하나 또 배워간다.
