> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/dynamic-programming/tiling-2xn.md).

# Tiling 2xn

틀린 이유 

1. 일단 Top-down 재귀 방식으로 풀 건지, Bottom-Up 반복문으로 풀 건지 결정해야 한다.
2. 정답을 %10007로 나눠야하는데 나누지 않아서 틀렸다. 그래서 최종 해인 go(N)리턴값만 %10007로 바꾸니 또 틀렸다.\
   dp\[N] = go(N-1) + go(N-2);이다. 이 더해지는 두개의 값에 모두 %10007해주니까 정답처리된다.\
   \=>나무 재테크에서 값들 다 더하고 난 후 /2 한 값 != /2 먼저 하고 다 더한 값 다르듯이,\
   여기서도 비슷한 이치 아닐까 짐작한다..

Top-down은 문제를 가장 작은 문제로 쪼개고, 그 해를 dp배열에 저장해야한다.\
가장 작은 해는 dp\[0]과 dp\[1]이라고 할 수 있다. dp\[1] = 1이고, dp\[2] = 2이다. dp\[0]은 하나도 놓지 않는 방법을 1가지로 쳐서 1이라고 한다. 따라서 아래 코드에서 재귀함수의 재귀함수를 종료하는 리턴하는 조건은 N이 0이하일 때 0을 리턴하는 것이 아니라 N이 0일 때, N이 1일 때 dp\[0] = 1, dp\[1] = 1 저장해 놓고, 이후에 dp\[N]이 0보다 큰 값이 들어있다면 이것은 앞의 문제들로부터 해를 구해서 저장했다는 의미이므로 dp\[N]을 바로 리턴하면 된다. 아래의 정답코드를 참조하자.

```java
static int go(int N) {
 		if(N<=0) return 0;
 		if(dp[N]>0) return 0;//이미 채워진 경우
 
     //dp[N] = dp[N-1] + dp[N-2];
     dp[N] = go(N-1) + go(N-2);
     return dp[N];
}
```

정답 코드 : N=0,N=1일 때, dp배열에 값을 저장하고, 저장하고 난 후 dp\[N]을 리턴한다!\
이로써 dp\[2]가 구해지고, 재귀함수들이 리턴되면서 최종적으로 큰 문제의 해도 구할 수 있게 된다!

```java
package ss;
import java.util.Scanner;
public class Tiling_2N {
	static int dp[];
	static int go(int N) {
		if(N==0) dp[N]=1;
		else if(N==1) dp[N]=1;
		if(dp[N]>0) return dp[N];//이미 채워진 경우
		
		dp[N] = go(N-1)%10007 + go(N-2)%10007;
		return dp[N];
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		dp = new int[1001];
		
		System.out.println(go(N)%10007);
	}

}

```

![재귀함수가 실행되어 최종해가 구해지는 과정](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MlPWi0__eImy3LMd95i%2F-MlPY3yT8Errppz81ivx%2Fimage.png?alt=media\&token=ae2ed19c-5c83-4736-86d7-9af0b5d6a491)