백준 2748번( 자바 )
DP 로 피보나치 수 구하기
백준 2748번을 DP를 이용해 Java로 풀어봤다.
역시 이번에도 알고리즘 공부 시작한 지 얼마 안 된 티가 나는 실수를 해서 삽질을 짧게나마 했다...^^
문제 조건대로면 90번째 피보나치수까지 커버를 해야 하는데, int
형으로 받아서 계속 틀렸던 거다. 실제로 90번째 피보나치수를 구해보니 int
범위를 한참 벗어난다... long
으로 바꿔주자마자 해결이 됐다.
아직 갈 길이 멀구나~...
짧게 요점만 적으면, 이미 계산했던 전력이 있는 놈을 다시 계산해주지 않는 것이 핵심
이고 이를 위해서 배열
을 사용한다.
아래는 내가 제출한 코드다.
import java.util.*;
import java.io.*;
public class boj2748 {
static int n;
static long[] dp = new long[91];
static long fib(int n){
if(dp[n]==-1)
dp[n] = fib(n-1) + fib(n-2);
return dp[n];
}
public static void main(String args[]) throws IOException {
BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(bfr.readLine());
for(int i=0; i<91; i++)
dp[i] = -1;
dp[0] = 0; dp[1] = 1;
System.out.println(fib(n));
}
}
개빡친다...^^
오늘 배운 것
결괏값의 범위를 반드시 생각하고 변수의
type
을 정하자!
Author And Source
이 문제에 관하여(백준 2748번( 자바 )), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@topqr123q/백준-2748번-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)