[JAVA] 백준 2193번 【이친수】

---

패턴을 파악하기 위해서 트리구조로 그려보았다.

 

그랬더니, 위와 같이 파악할 수 있었고, 피보나치 수열이구나 깨달았다.

 

Dp[1] = 1

Dp[2] = 1

Dp[3] = 2

Dp[4] = 3

Dp[5] = 5

 

경우의 수를 적어보기만 했어도, 피보나치임을 예측했을 것 같다..ㅎㅎ

 

아무튼 Dp[i] = Dp[i-1]+Dp[i-2] 점화식을 사용하면 문제는 매우 간단하게 해결된다!

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		long [] Dp = new long[N+2];
		Dp[1]=1;
		Dp[2]=1;
		for(int i=3;i<=N;i++) {
			Dp[i]=Dp[i-1]+Dp[i-2];
		}
		System.out.println(Dp[N]);
		}
	}

 

데이터가 오버플로우가 발생할 수 있기 때문에 long 타입의 Dp를 생성하는게 중요하다.