백준 11727 : 2xn 타일링2

 문제

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

11727 2xn 타일링2

 

 구현 방법

위의 계산을 통해 dp[N] = dp[N-2]*2 + dp[N-1] 임을 알 수 있습니다.

10007로 나눈 나머지를 출력해줘야 되기 때문에 dp에 값을 저장할 때부터 나눈 값을 저장해줍니다.

출력할 때 나누어 주면 수가 int 범위를 넘어서기 때문에 미리 저장하여 나눠줍니다.

 

 구현 코드

package BOJ.Silver.dp;

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

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

 

정답!