[백준] 2133번(타일 채우기)

백준 2133번

최종 제출 코드

n = int(input())

if n%2 != 0:
  print(0)

else:
  dp = [0]*(n//2)
  dp[0] = 3
  
  for i in range(1, n//2):
    ele = 0
    for j in range(i-1):
      ele += dp[j]*2
    ele += dp[i-1]*3
    dp[i] = ele+2
  print(dp[-1])

.
◼ N이 홀수이면 2X1 타일을 사용해서 채울 수 없음

• 이 경우 0을 출력

.
◼ N이 짝수일 때 경우의 수 구하기

• 폭이 2일 때 타일의 경우의 수는 3이며, 2를 제외한 모든 짝수일 때는 경우의 수가 2이다.
• N을 짝수로 분할할 수 있는 경우의 수를 먼저 구한다.
  ⇒ ex) 2 : (2), 4 : (2, 2), (4), 6 : (2, 2, 2), (4, 2), (2, 4), (6) ...
• n번째 원소일 경우, n-1번째 원소의 값 * 3 + n-2번째 원소의 값 * 2 + ... + 1번째 원소의 값 * 2 + 2가 원소의 값이 된다.