백준 2133번 - 타일 채우기 / Java

문제

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

2133번: 타일 채우기

기존 타일 채우기 문제는 2*n 이었지만 3*n으로 늘었다.

세로에 3만큼의 크기를 채워야하므로 n이 홀수 일때는 타일을 채울 수 있는 경우의수가 없다.

또한 n이 2씩 늘어날때마다 만들수 있는 방법이 2가지씩 늘어나는 것에 유의해서 점화식을 세우면 된다.

 

알고리즘

1. 기본적으로 dp[i] = dp[i-2]*3 이라는 점화식을 세운다(2*n일때의 점화식)

2. 하지만 세로가 3이므로 i가 짝수번째일때마다 새로운 규칙의 방법을 추가해준다

소스코드

/*
 * BOJ2133
 * 2020.01.20
 * Hyeonseong
 */
import java.util.*;
public class BOJ2133
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Solution{
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] dp = new int[31];
        dp[0] = 1;
        dp[2] = 3;
        if(n>=4) {
            for(int i=4;i<31;i+=2) {
                dp[i] = dp[i-2]*3;
                for(int j=4;j<=i;j+=2) {
                    dp[i] += dp[i-j]*2;
                }
            }    
        }
        System.out.println(dp[n]);
    }
}