[JAVA]백준 11727번: 2×n 타일링 2

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

11727번: 2×n 타일링 2

 

 

 

 

| 문제 해결방법

 

관련 알고리즘 : DP

 

규칙 찾기

나의 풀이 방법은 n이 홀수인 경우와 짝수인 경우를 나누어 계산한다.

 

 

n=1인 경우는 단 한 가지

n=2인 경우는 세 가지

 

 

 

 

n=3인 경우

 

n이 홀수일 경우의 규칙은 바로 전에 구한, n=2일때의 타일들에 맨 앞, 맨 뒤에 하나의 타일을 붙여주는 것이다.

 

이 경우 2x1 타일로만 이루어진 경우가 중복해서 나오기 때문에 -1을 해준다.

 

f(3) = f(2) * 2 - 1

 

 

 

n=4인 경우

 

 

 

n이 짝수인 경우에는 n-2인 n=2일때의 경우에 가능한 두 타일의 경우를 각각 더해주고,

 

 

 

2x1 타일을 앞 뒤로 배치했을 경우에 

내부에 올 수 있는 n-2가지 경우를 더해주었다.

 

그리고 여기서도 발생하는 중복(2x1 타일로만 이루어진 경우)을 제거해주기 위해 -1 해준다. 

 

f(4) = ( f(2) * 3 ) +  ( f(2) - 1 ) = f(2) * 4 - 1

 

 

[JAVA] 해설 코드

 

import java.util.Scanner;

public class Main {

	static int div = 10007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long[] dp = new long[n+1];
		dp[0]=1;
		dp[1]=1;
		for(int i=2;i<=n;i++) {
			// 짝수인 경우
			if(i%2==0)
				dp[i] = (dp[i-2]*4-1)%div;
			// 홀수인 경우
			else 
				dp[i] = (dp[i-1]*2-1)%div;
		}
		System.out.println(dp[n]);
	}

}

 

 

[제출] 메모리 및 시간