[baekjoon] 백준 2133번(파이썬): 타일 채우기

문제

2133번: 타일 채우기

알고리즘

- 타일을 만들어 내면서 점화식을 생성한다.

- 반복문을 통해 점화식을 수행한다.

점화식을 구하는 과정을 아래에 작성해보았다.

• dp[2] => 3 * 2인 경우

머리로 생각해내서 타일을 만들어 볼 수 있다.

• dp[3] => 3 * 3인 경우
  

만들 수 있는 타일이 없다. 이때 홀수는 만들 수 없는 것으로 판단했다.

 

• dp[4] => 3 * 4인경우

3 * 2를 2개 쓴다. (dp[2] * 2)

9가지 이후, 위 두 모양의 특수한 모양 2개를 추가한다.

 

• dp[6] => 3 * 6인 경우

1) 3 * 4짜리에 11개가 들어가고 3 * 2짜리에 3가지가 들어갈 수 있으므로 11 * 3(dp[4] * dp[2])

2) 특수한 모양 두 개에 3가지씩 들어가므로 3 * 2(dp[2] * 2)

3) 3 * 6일 때만 나오는 특수한 모양 2개를 포함해서(dp[6] += 2)

11*3+3*2+2=41이 나온다.

따라서 점화식은 dp[n] = dp[n - 2] * dp[2] + dp[n - 4] * 2 ... + 2이다.

코드

import sys

# 1 => 0
# 2 => 3 = 3
# 3 => 0
# 4 => dp[2] * dp[2] + 2 = 11
# 5 => 0
# 6 => dp[4] * dp[2] + dp[2] * 2 + 2 = 41
# 7 => 0
# 8 => dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2 = 153
# 점화식 : dp[n] = dp[n - 2] * dp[2] + dp[n - 4] * 2 ... + 2

n = int(sys.stdin.readline())
dp = [0] * 31
dp[2] = 3

# 반복문을 통해 점화식을 수행
for i in range(4, n + 1):

    # 짝수만을 타일로 채울 수 있다.
    if i % 2 == 0:
        dp[i] += dp[i - 2] * dp[2]

        for j in range(i - 4, -1, -2):
            dp[i] += dp[j] * 2 # dp[j]에 특수한 모양 2개의 조합

        dp[i] += 2 # 특수한 모양 2개 추가

print(dp[n])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법