11726_2×n 타일링

사용 알고리즘: DP

사용 언어: java

 

package week33;

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[][] dp = new int[n+1][3];
		dp[1][1] = 1;
		dp[1][2] = 0;
		if(n == 1) {
			System.out.println(1);
			return;
		}
		dp[2][1] = 1;
		dp[2][2] = 1;
//		dp[3][1] = 1+1; //dp[i-1][1] + dp[i-1][2]
//		dp[3][2] = 1; //dp[i-2][1] + dp[i-2][2]
		
		for(int i=3; i<n+1; i++) {
			dp[i][1] = (dp[i-1][1] + dp[i-1][2]) % 10007;
			dp[i][2] = (dp[i-2][1] + dp[i-2][2]) % 10007;
		}
		
		System.out.println((dp[n][1] + dp[n][2]) % 10007);
	}

}

 

 

그으으 이렇게 이차원으로 풀지 않으면 내 머리론 이해가 잘 안 된다.

풀었음 됐지 머