[알고리즘/DP] 2133번 : 타일 채우기 - python

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

2133번: 타일 채우기

 

---

• 문제
• 소요시간: 30분 실패

---

• 설계하기(접근방법) 

1. 입력받기

n 을 입력받는다

2. 구현하기

 

가로가 2인 직사각형은 쉽게 구할 수 있다

총 3가지가 나온다

 

가로가 4인 직사각형까지 구했지만

사실 6..8...10 쭉쭉 직사각형이 하나씩 들어난다

 

점화식이 처음에 어려웠는데 그림을 그려보니 이해가 되었다

 

dp[2] = 3

 

dp[4] = dp[2] * 3 + (4짜리 직사각형 2가지 케이스)

 

dp[6] = dp[4] * 3 + dp[2]에다가 4짜리 직사각형 -> dp[2] * 2 + 6짜리 직사각형

 

.....

즉 계속 더해나가면 된다

 

3. 출력하기

dp[n]을 출력한다

 

---

• 코드(출력)

n = int(input())
dp = [0] * 31
dp[2] = 3

for i in range(4, 31, 2):
    dp[i] += dp[i - 2] * 3 + 2
    for j in range(4, i, 2):
        dp[i] += dp[i-j] * 2

print(dp[n])

---

• 얻어갈 부분

1. 쉬운 문제인줄 알았으나 역시 난이도가 높은 문제였다