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

타일 채우기 - 백준 2133번

문제

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

입력

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

출력

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

풀이

• dp[1]
  • n = 3 일 때, 경우의 수 : 3
    • dp[1] = 3
• dp[2]
  • n = 4 일 때, 경우의 수 : 11
    • dp[1] * dp[1]
    • + 2 ( 새로운 모양 2개 )
• dp[3]
  • n = 6 일 때, 경우의 수 : 41
    • dp[1] * dp[2]
    • + dp[2] * 2 ( dp[2] * 새로운 모양 )
    • + 2 ( 새로운 모양 2개 )
• dp[4]
  • n = 8 일 때, 경우의 수 : 153
    • dp[1] * dp[2]
    • + dp[3] * 2 ( dp[2] * 새로운 모양[2] 2개 )
    • + dp[2] * 2 ( dp[1] * 새로운 모양[3] 2개 )
    • + 2 ( 새로운 모양 2 )

'''최종 수식'''
dp[n] = dp[1] * dp[n-1]
dp[n] += dp[n - i] * 2 for i in range(1, i)
dp[n] += 2

코드

def solution(N):
  dp = [0, 3]
  if N % 2 == 0:
    N //= 2
    for i in range(2, N + 1): # dp[n] = dp[1] * dp[n-1]
      dp.append(dp[1] * dp[i-1])
      for j in range(2, i): # dp[n] += dp[n - i] * 2 for i in range(1, i)
        dp[i] += dp[i - j] * 2
      dp[i] += 2 # 새로운 모양
    return dp[N]

  return dp[0]

N = int(input())
print(solution(N))