/ BOJ

BOJ_2193_이친수_JAVA

문제 : 이친수

링크 : BOJ_2193_이친수

접근 방식

경우의 수를 하나하나 다 따져봤더니, 결국 이 문제도 피보나치 수열 문제였다.

  1. 1일 때 1으로 1개
  2. 2일 때 10으로 1개
  3. 3일 때 100, 101으로 2개
  4. 4일 때 1000, 1001, 1010으로 3개
  5. 5일 때 10000, 10001, 10010, 10100, 10101 5개 …

벌써 익숙하다. 피보나치수열이다.

소스 코드

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

public class BOJ_2193_이친수 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		long dp[] = new long [N+1];

		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]);
	}

}