백준 2193, 이천수

문제

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

문제풀이

n	pinary number	output
1	1	1
2	10	1
3	100, 101	2
4	1000, 1001, 1010	3
5	10000, 10001, 10010, 10100, 10101	5
6	100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010	8

n의 수에 따른 n자리의 이천수의 개수는 피보나치 수를 따르는 것을 알 수 있습니다.

 

소스코드

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


public class Main {
	public static long solution(long[] dp, int n)
	{
		if(dp[n]!=0)
		{
			return dp[n];
		}
		
		if(n<=2)
		{
			dp[n] = 1;
		}else {	
			dp[n] = solution(dp, n-1) + solution(dp, n-2);
		}
		return dp[n];
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long[] dp = new long[n+1];
		System.out.println(solution(dp,n));
	}
}