백준 11726

피보나치라는 것만 알면 간단!

 

그런데 피보나치라는 걸 몰라서 헤맸다.....

---

s(n) 을 2xn 크기의 직사각형을 채우는 방법의 수라고 정의하면,

s(n-1)의 형태에다가 오른쪽에 1x2 타일을 붙이는 경우가 포함되는 걸 알 수 있다.

따라서 s(n) = s(n-1) + ?

 

이 때 ?의 형태들을 잘 보면, 2x1 타일이 두개 붙은 것이 가장 오른쪽에 들어가있다.

즉, s(n-1)에서 1x2 타일이 항상 가장 오른쪽을 차지하고 있었다면

나머지 경우의 수들은 2x1 타일이 항상 가장 오른쪽을 차지하고 있다.

즉, ? = s(n-2).

 

따라서 s(n) = s(n-1) + s(n-2)

 

어차피 n이 되기 전 모든 값들을 계산해야 할테니 memoization을 해도 생략할만한 계산이 없다.

따라서 tabulation을 사용해서 코드 짬.

 

==>그리고 10007은 소수라서 나머지 값을 dp에 저장해도 연산에 차이는 없다!

 

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

public class Baekjoon_11726 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
				
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		
		int[] dp = new int[1001];
			//여기서 num+1로 주면 ArrayIndexOutOfBounds
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3; i <= num; i++) {
			dp[i] = (dp[i-1] + dp[i-2])%10007;
		}
		
		System.out.println(dp[num]);
	}
}

주의할 점은 dp의 길이를 num+1로 했다가는 dp[2] = 2 때문에 ArrayIndexOutOfBoundds에 걸린다는것!