[백준 2133] 타일 채우기 / 자바 / dp

문제         

레벨: G4
알고리즘: dp(업데이트 기준x + 일차원 배열)
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

 

확실히 dp는 고급 알고리즘이다. 이 만큼 내 머리를 아프게 하는 알고리즘은 없다. 
전에도 말했지만 dp의 시작은 점화식을 세우는 것이고
점화식을 세우는 것은 직접 예시를 구해보는 것이다. 그리고 그 사이에 관계를 찾아내는 것이다.

이문제는 너비가 4이후부터 특수모양의 경우의 수가 2개 생긴다는 것을 기억해야 한다.

아래 링크에서 그림을 참고해봐라.
찾아본 것 중 가장 이해가 쉽게 될 그림이다.
https://january-diary.tistory.com/entry/BOJ-2133-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-JAVA

import java.io.*;
import java.util.*;
 
public class Main {
   public static void main(String[] args) throws IOException {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      if(N%2==1){
         System.out.println(0);
         return;
      }
 
      int[] dp = new int[N+1];
      dp[2] = 3;
      for(int i=4;i<=N;i+=2){
         dp[i] = dp[i-2]* dp[2] + 2;    //이전 너비의 경우의 수 x 너비 2 경우의 수  + 자기 특수 모양
         for(int j=i-2;j>=4;j-=2){  //j를 특수 모양의 너비라고 생각하면 됨
            dp[i] += dp[i-j]*2;
         }
      }
 
      System.out.println(dp[N]);
   }
}