beeimp
BeeImp
beeimp
전체 방문자
오늘
어제
  • 분류 전체보기 (110)
    • Program_Language (17)
      • Python (13)
      • Go (0)
      • JavaScript (4)
      • TypeScript (0)
      • Rust (0)
      • Solidity (0)
    • OS (8)
      • UNIX&LINUX (7)
      • Windows (0)
      • MacOS (1)
    • Front-End (19)
      • Svelte (19)
      • React (0)
    • Blockchain (6)
      • Bitcoin (0)
      • Ethereum (1)
      • Klaytn (0)
      • Project (5)
    • Data Structure&Algorithm (11)
      • Greedy (7)
      • Dynamic Programming (1)
      • Sort (0)
      • DFS & BFS (2)
      • Recursive (1)
    • Security (0)
      • SDP (0)
      • Authentication (0)
    • Network (3)
      • OpenWrt (0)
      • SDN&NFV (1)
    • Git (5)
    • IT_News (0)
    • 베타 학습단 (12)
      • SQL (12)
    • Project (1)
    • Issues (1)
    • Reviews (3)
    • I Learned (23)
      • TIL (23)
      • WIL (0)
    • Other (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • solidity
  • Docker
  • greedy
  • ubuntu
  • 기초
  • svelte
  • Nest.js
  • github
  • PYTHON
  • Git
  • 탐욕법
  • Ethereum
  • javascript
  • 블록체인
  • mysql
  • jenkins
  • react
  • typescript
  • sql
  • blockchain

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
beeimp

BeeImp

Data Structure&Algorithm/Dynamic Programming

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

2021. 7. 14. 17:51

타일 채우기 - 백준 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))

    티스토리툴바