백준 2193번 : 이친수

 문제

www.acmicpc.net/problem/2193

2193번: 이친수

2193 이친수

 

 구현 방법

점화식을 구해보면 dp[N] = dp[N-2] + dp[N-1] 임을 알 수 있습니다.

다만 N이 90까지이므로 int 범위를 넘어서 dp 배열을 long 타입으로 선언해줘야 합니다.

 

 구현 코드

package BOJ.Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

 

정답!