[백준] 2133번 타일 채우기 - 파이썬, 자바

🔈 문제

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

 

📝입력

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

 

📑출력

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

 

📚 문제 풀이

 

dp 점화식을 찾아내는 문제였다. 전형적인 dp 문제.

 

위의 사진이 N이 12일 때의 한 경우이다.

그림을 조금 그려보면 N이 홀수일때는 2X1, 1X2 타일로 벽을 전부 채울 수 없다. 때문에 N이 홀수면 경우의 수는 0이 된다.

N이 2일 때는 3가지의 경우의 수가 등장한다.

그림퀄리티가 낮지만..ㅎㅎ

N이 4일 때는 총 11가지의 경우의 수가 등장하는데 N이 4일 때만 나올 수 있는 경우의 수 2개랑 N이 2일 때의 경우의 수인 3을 제곱한 결과이다.

처음에는 이렇게 생각하여 점화식을 적었는데 틀렸습니다 판정을 받았다.

 

결국 질문하기의 도움을 받아 점화식을 작성했다.

점화식은 다음과 같다.

dp[N] = dp[N-2]*4 - dp[N-4] (N % 2 == 0)

 

💻 코드

파이썬

n=int(input())
dp=[1,0,3]+[0]*(n-2)
for i in range(4,n+1,2):
    dp[i]=dp[i-2]*4-dp[i-4]
print(dp[n])

 

자바

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.valueOf(br.readLine());
        
        long[] dp = new long[n+1];
        dp[0] = 1;
        if (n > 1) {
            dp[2] = 3;
        }
        for (int i=4; i<=n; i=i+2) {
            dp[i] = dp[i-2]*4 - dp[i-4];
        }
        System.out.println(dp[n]);
    }
}

 

🍭 시행착오

자바가 아직 익숙하지 않지만 그래도 재미있다 ㅎㅎ

 

런타임에러는 N이 1일때, dp[2] 의 초기값 세팅을 하여서 발생하였다.

 

🔗 문제링크 타일 채우기

2133번: 타일 채우기