[프로그래머스(Programmers)][자바(java)] (Lv4) 3 x n 타일링

 

https://programmers.co.kr/learn/courses/30/lessons/12902

코딩테스트 연습 - 3 x n 타일링

 

문제 풀이

 

( 비슷한 문제를 백준에서 풀어본 적이 있음. https://www.acmicpc.net/problem/2133 다른 코드 참고함 )

 

public class Solution {
	
	public int solution(int n) {
		final int r = 1000000007;
		long dp[] = new long[n+1]; int i, j;
		if( n % 2 == 0 ) {
			dp[0] = 1; dp[2] = 3;
			for( i = 4; i <= n; i+=2 ) {
				dp[i] = (3 * dp[i-2]) % r;
				for( j = 4; j <= i; j+=2 )
					dp[i] = ( dp[i] + ( ( 2 * dp[i-j] ) % r ) ) % r;
			}
		}
		return (int)dp[n];
	}
}

 

가로의 길이 n이 홀수일 경우 타일을 완벽히 채울 수 없으므로 경우의 수가 0임 ( 빈 공간이 생김 )
n이 짝수일 때만 동적계획법을 이용하여 타일을 채울 수 있는 경우의 수를 구함

가로가 2일 경우 => 3가지

가로가 4일 경우 => 11가지

 

n	dp[n]
2	3^1	3
4	(3^2)+2 = 11	2,2 / 4
6	(3^3)+((3*2)*2)+2 = 41	2,2,2 / 2,4(4,2) / 6
8	(3^4)+((3*3*2)*3)+((3*2)*2)+(2*2)+2 = 153	2,2,2,2 / 2,2,4(2,4,2)(4,2,2) / 2,6(6,2) / 4,4 / 8