백준 11727 - 2×n 타일링 2

Java

11727 번 - 2×n 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

접근 방법

2×n 타일링 1의 문제에서, 2x2 타일이 추가 되었다.

현재 길이 i에서 (i <= n) 타일은 i - 1개 길이의 타일에서 1x2를 하나 추가한 것이며, i - 2개 길이의 타일에서 1x2 그리고 2x2의 타일을 추가한 것이다.
따라서 점화식으로 표현하면, dp[i] = dp[i - 1] + dp[i - 2] * 2가 된다.
문제에서 10007로 나눈 나머지를 출력하라 했으므로, 점화식 계산 후에 10007로 %연산을 한다.

코드

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

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	
    	int[] dp = new int[n + 1];
    	
    	dp[1] = 1;
    	if(n >= 2)
    		dp[2] = 3;
    	
    	for(int i = 3; i <= n; i++) {
    		dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
    	}
    	
    	System.out.println(dp[n]);
    	br.close();
	}

	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

모듈로를 적용한 값끼리 더한 것은, 두 값을 더하고 모듈로를 적용한 값과 동일하다는 것을 알았다.

개선할 점

없습니다.