백준 11727 2xn 타일링 2 JAVA (DP)

1. 문제

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

2. 설명

하나씩 해보면서 규칙찾아서 풀었다.

짝수일 때는 그 전의 dp 2배에 +1을 해주어야 했고,

홀수일 때는 전의 dp 2배에 -1을 해주어야 했다.

규칙만 찾으면 쉽게 풀 수 있는 문제

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] dp = new int[1001];
		int mod = 10007;
		
		dp[1] = 1;
		for(int i=2; i<=n; i++) {
			if(i%2==0) // 짝수면 +1
				dp[i] = (dp[i-1] * 2 + 1) % mod;
			else // 홀수면 -1
				dp[i] = (dp[i-1] * 2 - 1) % mod;
		}
		
		System.out.println(dp[n]);
	}
}