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

🔺 문제

2133번: 타일 채우기

 

 

🔺 코드

import java.util.*;
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());
        
        long[] dp = new long[N + 1];
        
        // 홀수일 경우, 채울 수 없으므로 0 출력하고 종료
        if(N % 2 != 0) {
            System.out.println(0);
            return;
        }
        
        // N은 짝수만 가능
        dp[0] = 1;    // 아무 것도 채우지 않는 경우
        dp[2] = 3;
        
        for(int i = 4 ; i <= N ; i += 2) {    // 짝수만 가능하므로 2씩 증가
            dp[i] = dp[i - 2] * dp[2];
            
            for(int j = i - 4 ; j >= 0 ; j -= 2) { // 예외 케이스 더하기
                dp[i] += (dp[j] * 2); // 2는 예외 케이스
            }
        }
        
        System.out.println(dp[N]);
    }
}

✅ 해결 아이디어
✔ DP
- 점화식 : 그 전전 타일 만드는 방법 수 * 이전에 나타난 특별한 타일 개수(2)

---

💬 느낀 점

식 구하는 것이 너무나 어렵도다.....ㅠ

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

[JAVA/2133번] 타일 채우기

 

 

- 이 글 특히 짱,,,

[백준 2133번] 타일 채우기 - java