백준 2193번: 이친수 [DP] - Java

www.acmicpc.net/problem/2193

2193번: 이친수

이친수가 미친수로 읽히는 건 나뿐인걸까?

 

역시나 1~5자리의 경우의 수를 다 써보고 규칙을 발견..

[n] = [n-1]+[n-2]이다.

 

 

*주의점: n이 1이들어올때는 dp[2]를 세팅하게되면 런타임 에러가 나니 주의

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static long[] dp;
	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp = new long[n+1]; // 자리수 n일 때, 이친수의 수
		
		dp[1] =1;
		if(n>1)
			dp[2] =1;
		
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		
		System.out.println(dp[n]);
		
	}

}