[BJ11727] 2xn 타일링 2

타일링 1 말고 2부터 한 나 멋있어 ..

물론 풀이 봤지만

이 문제가 DP라고는 생각도 못했다.

 

이 문제는 그림을 그려보면 된다. 

타일 그림을 그러보면

 

N = 1 일 때는 1개,

N = 2 일 때는 3개,

N = 3 일 때는 5개,

N = 4 일 때는 11개가 된다.

 

규칙 = 전전 수 * 2 + 전 수 = 현재 수

 

따라서 DP 점화식으로 표현하면,

DP[N] = DP[N-1] + 2DP[N-2] 가 된다.

 

자바 코드 

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

public class Bj11727 {
	public static void main(String [] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        if (N == 1) {
            System.out.println(1);
            return;
        }
		long dp [] = new long[N];
		dp[0] = 1; //N=1일때 1개
		dp[1] = 3;
		for(int i=2;i<N;i++) {
			dp[i] = (dp[i-1]+ 2*dp[i-2]%10007);
		}
		System.out.println(dp[N-1]);
	}
}

주의할 점 

맞게 썼는데도 계속 실패라고 뜨는데 이유가 있었다. 

10007로 나눠주는 부분에서, 계속 dp를 다 더 해주고 나서 마지막에 값을 나눠주게 된다면 무지 큰 수가 나와서 잘못된 값이 출력될 수 있다.

따라서 dp를 계산할 때 나눠줘야 한다.