https://www.acmicpc.net/problem/15624
15624번: 피보나치 수 7
첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.
www.acmicpc.net
저는 DP를 통해 문제를 해결하였습니다.
피보나치 수와 같이 구현하고, DP를 통해 중복되는 계산을 반복하지 않도록 하였습니다.
package BOJ.dp;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class BOJ_15624 {
private static final int LIMIT = 1_000_000_007;
private static final int NOT_VALID = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n+1];
int result = cal(n,dp);
System.out.println(result);
}
private static int cal(int n, int[] dp) {
if(n == 0){
return 0;
}
if(n == 1 || n == 2){
return 1;
}
if(dp[n] != NOT_VALID){
return dp[n];
}
return dp[n] = (cal(n-1,dp) + cal(n-2,dp)) % LIMIT;
}
}
'알고리즘' 카테고리의 다른 글
백준 1487번 물건 팔기 (JAVA) (0) | 2023.10.26 |
---|---|
백준 13302번 리조트 (JAVA) (0) | 2023.10.25 |
백준 1951번 활자 (JAVA) (1) | 2023.10.23 |
프로그래머스 수열과 구간 쿼리2(JAVA) (0) | 2023.10.22 |
백준 2312번 수 복원하기 (JAVA) (1) | 2023.10.21 |