백준 2193 다이나믹프로그래밍

백준 2193

N==1일땐 1

N==2일땐 1

N==3일땐 2

N==4일땐 3

N==5일땐 5 까지 직접 노트에 써보고 점화식이 f(N) = f(N-1) + f(N-2)라는걸 알아냈습니다.

그런데 제출을 해도 계속 틀렸다고 나왔습니다...

한동안 헤매다가 N에 90을 넣어봤는데 이상한 음수가 나오더군요.

값을 저장해둔 dp배열을 int형으로 선언해뒀는데 범위를 넘어가서 그랬습니다.

dp배열을 long으로 선언하고 문제를 해결했습니다.

 

아래는 제 코드입니다.

public class B2193 {
	private static int N;
	private static long dp[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		br.close();
		dp = new long[N+1];
		dp[1] = 1;
		if(N > 1) {
			dp[2] = 1;
		}
		if(N > 2) {
			for(int i = 3; i <= N; i++) {
				dp[i] = dp[i-1] + dp[i-2];
			}
		}
		System.out.println(dp[N]);

	}
}