algorithm/dp
boj 10826 피보나치 수 4
와이에쓰
2021. 2. 8. 21:27
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가
www.acmicpc.net
점화식 : dp[i] = dp[i - 1] + dp[i - 2]
앞의 두 개의 수를 더한 값이 자신의 값이 됩니다.
이 문제는 N이 10000까지 오기때문에 long의 범위를 초과합니다.
자바에는 BigInteger라는 클래스가 있기때문에 이용 사용하여 쉽게 구할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static void solve() {
BigInteger dp[] = new BigInteger[10001];
dp[0] = new BigInteger("0");
dp[1] = new BigInteger("1");
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1].add(dp[i - 2]);
}
System.out.println(dp[N]);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws Exception {
input();
solve();
}
}
|
cs |