문제 2133

소스코드

import java.io.*;
public class boj2133 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[31]; int[] DP = new int[31];
        DP[0] =1; DP[2] =3;
        for (int i = 4; i <=30 ; i+=2) {
            arr[i] = arr[i-2] + DP[i-4];
            DP[i] = DP[i-2] *3 + arr[i]*2;
        }
        System.out.println(DP[N]);
    }
}

풀이접근

1. 먼저 3xN 크기의 벽면이라는 부분을 집중하면, N이 홀수가 될 경우 전체 면적이 홀수가 되기 때문에 불가능하다는걸 알 수 있다.
2. 3x2의 경우를 먼저 살펴보면 해당 크기를 채울 수 있는 방법은 총 3가지가 된다.
   
3. N이 2보다 클 경우에는 해당 3x2를 왼쪽에 두고 나머지를 계산한다고 생각하면 DP[n] = DP[n-2]*3 ~~ 라는 점화식이 만들어질 것이다.
4. N이 4일 경우랑 6일 경우를 살펴보면
   상하대칭까지 생각해서 2개의 방법이 생긴다.'
5. 여기까지 경우를 살펴 보면서 DP[N] = DP[n-2]3 + (DP[n-4] + DP[n-6] ... DP[n-n])2라는 점화식을 생각할 수 있었다.
6. 문제에서 N은 30까지로 주어지기 때문에 30까지의 값을 DP에 저장하고 출력하는 형식으로 풀었다.

문제 핵심

• DP