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]을 바로 리턴하면 된다. 아래의 정답코드를 참조하자.

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]가 구해지고, 재귀함수들이 리턴되면서 최종적으로 큰 문제의 해도 구할 수 있게 된다!

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

}

재귀함수가 실행되어 최종해가 구해지는 과정