[백준 11726] 2xn 타일링 - 자바

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

11726번: 2×n 타일링

 

1. 풀이

---

처음에 문제만 보고는 당황하게 됩니다..

 

하지만 직접 1부터 세보면서 규칙을 보면 피보나치 수열이 되는 것을 볼 수 있습니다.

 

1 : 1

2 : 2

3 : 3

4 : 5

5 : 8

6 : 13

7 : 21

8 : 34

9 : 55

...

 

주의할 점은 입력값이 1일때도 1을 출력해서, memo의 크기를 입력값+1을 하게되면, 1을 입력했을때 문제가 됩니다. 

 

그러므로, 애초에 memo의 배열 크기를 입력값의 제한인 1000까지만 만들어주면 해결이 됩니다.

 

2. 코드

---

import java.util.*;

public class Main {
	
	static int[] memo;
	
	static int Fibo(int n) {
		if(n <= 2)
			return memo[n];
		if(memo[n] != 0)
			return memo[n];
		
		return memo[n] = (Fibo(n-2) + Fibo(n-1))%10007;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		memo = new int[1001];
		memo[1] = 1; memo[2] = 2;
		
		System.out.println(Fibo(num));
		
		sc.close();
		return;
	}
}