728x90
1. 문제
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.
2. 풀이
BigInteger타입을 사용하는 것 외에는 평소에 피보나치수 구하는 것과 동일하다.
dp[0]에 BigInteger.ZERO를 저장하지 않으면 null이 저장되어 있으므로 꼭 따로 저장해줘야 한다.
import java.io.*;
import java.math.BigInteger;
public class BOJ_10826_피보나치수4 {
public static void main(String[] args) throws IOException {
BigInteger[] dp = new BigInteger[10001];
dp[0] = BigInteger.ZERO;
dp[1] = dp[2] = BigInteger.ONE;
for(int i=3;i<10001;i++) dp[i] = dp[i-1].add(dp[i-2]);
System.out.println(dp[Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine())]);
}
}
3. 결과
0을 챙기지 않아서 한 번 틀렸다.
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 15990 1,2,3 더하기 5 - JAVA (0) | 2023.07.09 |
---|---|
[BOJ] 16194 카드 구매하기 2 - JAVA (0) | 2023.07.08 |
[BOJ] 1043 거짓말 - JAVA (0) | 2023.07.04 |
[BOJ] 2011 암호코드 - JAVA (0) | 2023.07.03 |
[BOJ] 1516 게임 개발 - JAVA (0) | 2023.07.02 |
댓글