공부 144일차: 백준 2133번 타일 채우기 자바 java

2133 타일 채우기

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

2133번: 타일 채우기

 

 

 

---

백준 2133번 문제 타일 채우기

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/238

공부 121일차: 백준 11726번 2Xn 타일링 자바 java

이 문제와 비슷해 보이지만 훨씬 복잡하다

 

일단 n이 홀수면 절대 완성될 수 없으므로, 홀수인 경우는 모두 0이다

 

그림을 그려보면 다음과 같다

 

그래서 단순하게 점화식은 dp[i] = dp[i-2] * 3 으로 생각했다가 틀린 코드

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];
        dp[0] = 1;    // dp[2] = dp[0]*3 = 3 -> dp[0] = 1(아무것도 채우지 않는 경우를 1로 보자고 친다)
        
        for(int i = 2; i < n+1; i+=2) {
            dp[i] = dp[i-2] * 3;
        }
 
        System.out.println(dp[n]);
    }
 
}

 

https://yabmoons.tistory.com/536

이 블로그의 설명이 자세해서 도움을 많이 받았다

 

틀린 이유는 3x4일 때, 9가 아니라 11이기 때문이다

이 두 모양이 변수로 작용한다

 

그래서 위의 문제에서 높이만 +1 된 거니까 아래에 2x1 블럭을 놓는다고 가정해도 괜찮다고 생각했는데, 이것 역시 변수가 너무 많았다(3x4로 가정할 때부터 이미 맞지 않았다)

 

최종 점화식은

dp[i] = dp[i-2]*3 + (dp[i-4]*2) + (dp[i-6]*2) + (dp[i-8]*2) + ... (dp[0]*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];
        dp[0] = 1;    // dp[2] = dp[0]*3 = 3 -> dp[0] = 1(아무것도 채우지 않는 경우를 1로 보자고 친다)
        
        for(int i = 2; i < n+1; i+=2) {
            dp[i] = dp[i-2] * 3;
            for(int j = i-4; j >= 0; j-=2) {
                dp[i] = dp[i] + (dp[j]*2);
                // 점화식 : dp[i] = dp[i-2]*3 + (dp[i-4]*2) + (dp[i-6]*2) + (dp[i-8]*2) + ... (dp[0]*2) 
                // == dp[i] = dp[i] + (dp[i-4]*2) + (dp[i-6]*2) + (dp[i-8]*2) + ... (dp[0]*2)
            }
        }
 
        System.out.println(dp[n]);
    }
 
}

 

점화식 구하는 과정이 매우 복잡했던 문제다

 

 

 

 

---