[DP] 백준 2133 타일채우기 python

📄 백준 2133 타일채우기 📄

www.acmicpc.net/problem/2133

2133번: 타일 채우기

🤔 문제 풀이  🤔

n = 2일 때, 2 x 1, 1 x 2타일로 3 x 2 타일을 만들 수 있는 갯수를 세어보면 3가지 경우의 수가 나온다.

n = 3일 때, 홀수일때는 어떠한 타일도 만들 수 없다.

 

n = 4일 때는 2가지의 새로운 경우의 수를 찾을 수 있다.

n = 6일 때 또한 2가지의 새로운 경우의 수를 찾을 수 있다.

이렇게 짝수로 증가하는 n에서는 모두 2가지의 새로운 경우의 수를 찾을 수 있다.

 

dp[0] = 1, 아무것도 없는 경우의 수 하나

dp[2] = 3, 3가지 경우의 수

 

dp[4] = dp[2] * 3, + dp[0] * 2, n = 4일때는 2일때 나올 수 있는 경우의 수에 3가지 경우의 수를 곱해주고 2가지 경우의 수가 더 나올 수 있다.

dp[6] = dp[4] * 3 + dp[2] * 2, n = 6일때는 타일 크기 4를 사용해서 새로운 경우의 2가지가 나오므로 n = 2의 경우의 수에 2를 곱한 값을 더해준다.

이 작업을 입력받은 n까지 반복한다.

 

⌨️ 코드 ⌨️

n = int(input())

def sol(n):
    if n % 2 != 0:
        return 0
    else:
        dp = [0] * (n + 1)
        dp[0] = 1  # 0줄인 경우는 아무것도 안하는 경우 하나이니까
        dp[2] = 3
        for i in range(4, n + 1):
            dp[i] = dp[i - 2] * 3
            for j in range(i - 4, -1, -2):
                dp[i] += dp[j] * 2
        return dp[n]

print(sol(n))