[백준] DP - 2133번, 타일 채우기 (다른 풀이 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

문) 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입) 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출) 첫째 줄에 경우의 수를 출력한다.

---

풀이

1. 테이블 정의 : dp[i] = 경우의 수

2. 점화식

dp[i] = dp[i-2] * dp[2] +{ dp[i-4]*2 + dp[i-6]*2 + ... + dp[0] *2 };

 

3xn 타일이기 때문에, 짝수만 가능하다.

위의 점화식은 쉽게 말하면,

직전 값 * dp[2] 과 2씩 감소시켜 i가 0이 될 때까지한 수열을 더하는 것이다.

 

<점화식 도출 내용>

(3x2 타일) 3
(3x4 타일) 11
(3x2 경우의 수)² + (예외의 경우) = 9 + 2 = 11

(3x6 타일) 41
(3x4 경우의 수)*(3x2 경우의 수) + (3x2 경우의 수)*(기존 예외 케이스) + (그 밖의 예외 경우) = 33 + 3*2 + 2 = 41

 

▶ 3x2 타일 조합을 계속 돌려쓰면서, 새로운 예외 케이스 추가.

dp[2] = 3,

dp[i] = dp[i-2]*dp[2] + { dp[i-4]*2 + ... + dp[0] *2 };

 

3. 초기값 : dp[0] = 1;

점화식을 위하여 dp[0]을 1로 설정한다.

dp[1] = 0; // 해당 경우의 수가 존재하지 않는다. 같은 이유로, 홀수 n값은 0으로 return 해준다.

dp[2] = 3; // dp[2]값을 활용하여 쓰기 때문에 적어둔다.

 

스스로 어디까지 풀었나?

• 짝수만 가능하다는 조건.
• dp[2] 조합으로 dp[4]를 만들고, 그외에 예외 케이스가 2개가 있다.

여기까지 발견하고 dp[6]을 해보려는데 너무 경우의 수가 많아서 생각이 멈췄다.

이후, 과거 2xn 타일링처럼 n을 1과 2의 합으로 봐야하나? 라는 발상이 더 생각을 꼬이게 했다.

조금 더 사고를 발전시켰으면 좋았을 것이라는 아쉬움이 남는다.

 

코드

import java.io.*;
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());

        int[] dp = new int[n+1];

        //n이 홀수라면 0 출력
        if (n % 2 != 0) {
            System.out.println(0);
            return;
        }
		//초기값
        dp[0] = 1;
        dp[1] = 0;
        dp[2] = 3;
        for(int i=4; i<=n; i+=2) {
            dp[i] = dp[i-2] * dp[2];
            for(int j= i-4; j>=0; j-=2) {
                dp[i] = dp[i] + (dp[j] * 2);
            }
        }
        System.out.println(dp[n]);
        br.close();
    }
}

---

주어진 문제의 경우의 수를 차분히 나열하면서 규칙성을 발견해보자.

과거 문제를 참고하는 것도 도움되겠지만, 현재에 집중하자.

규칙성을 수식으로 풀어나가려는 노력을 더 해보자.

 

dp문제를 대하는 저의 결심입니다. 하하.

 

해도해도 익숙해지지 않지만, 그래도 부단히 노력해야겠다고 다짐하게 됩니다.

여러분도 파이팅

 

[참고] https://pangtrue.tistory.com/310

https://velog.io/@newtownboy/JAVA2133%EB%B2%88-%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0