[JAVA/백준/2133] 타일 채우기 / DP

 

2133번: 타일 채우기

 

풀이 과정

1. 모양의 종류

2칸일 경우 아래처럼 세 가지 종류로 만들 수 있다

 

4칸일 경우 2칸짜리 조합 * 2개로 만들 수 있다

하지만 추가적으로 4칸 이상 부터는 중간이 겹쳐진 특별한 모양이  두 개 존재한다

이는 6칸에서도 마찬가지로 존재하며 두 개씩 존재한다

 

 

2. 규칙 찾아 점화식 세우기

규칙을 찾아야 하는 DP 문제처럼 보이면 나는 바로 그림을 그려본다

아래 그림처럼 n=8 까지 그려서 규칙을 찾았다

 

f(n) = 2 + f(n-2)*3 + f(n-4)*2 + f(n-6)*2 + ... + f(2)*2 (n>=4)

 

추가적으로 n이 홀수일 경우에는 만들 수 없었다

 

 

결과 코드

위에서 도출한 식을 그대로 코드로 옮겨 Dynamic Programming 알고리즘으로 풀었다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    long[] dp = new long[31];
    dp[2] = 3;

    // f(n) = 2 + f(n - 2) * 3 + f(n - 4) * 2 + f(n - 6) * 2 + ... + f(2) * 2
    for (int i = 4; i <= N; i += 2) {

      int sigma = 0;
      for (int j = 2; j <= (i - 2) / 2; j++) {
        sigma += dp[i - 2 * j] * 2;
      }

      // 최종 식
      dp[i] = 2 + dp[i - 2] * 3 + sigma;
    }
    System.out.println(dp[N]);
  }
}