💯Problem Solving
[BOJ] 2133 타일 채우기
date
Aug 5, 2023
slug
boj-2133
author
status
Public
tags
Python
BOJ
summary
백준 0000번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 7, 2023 11:12 AM
문제 링크
문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
문제풀이
2xN의 타일 채우기와 유사한 문제,
처음에 2일때 → 3
다음 4일때 → 11 까지는 구했고
6일때 → 41까지는 구했다.
2→4넘어갈때 dp[n] = dp[n-2]*3 + 2인걸 알았고
4→6넘어갈때 dp[n] = dp[n-2]*3 + dp[n-4]*2 + 2인걸 알았는데
6→8넘어갈때 dp[n] = dp[n-2]*3 + dp[n-4]*2 + dp[n-6]*2 + 2 인것을 추측하지못해
빙빙 돌아갔다.
4를 알기 위해서는
2를 구해놓은 것에 3x2배열이 들어갈 자리 x3에 4의 특수모양 +2 를 해주면 가능하다.
6을 알기 우ㅐ허슨ㄴ
dp[4]를 구해놓은 것에 3x2배열이 들어갈 자리 x3에 (왼쪽 기준)
오른쪽 기준으로 4의 특수모양 * 3x2 = 배열이 들어갈 자리 dp[2]*2 에
특수모양을 오른쪽에 고정 시켜놓고 3x2배열을 왼쪽에서 돌리는 경우와 동일
6의 특수모양 + 2를 해주면된다.
8을 알기 위해서는
dp[6]을 구해놓은 것에 3x2배열이 들어갈 자리 x3 → 왼쪽 기준에
오른쪽 기준 6의 특수모양에 3x2 배열이 들어갈 자리 으로 dp[2]*2에
dp[4]를 구해 놓은 것에 3x4배열이 들어갈 자리, 즉 양옆으로
2*dp[4]
마지막으로 8의 특수모양 2를 더해주면된다.
파이썬 문제풀이 코드
N = int(input()) li = [1, 0, 3] for i in range(3, 31): if i % 2 == 0: result = 0 result += li[i-2] * 3 # 왼쪽만 처리 for j in range(i-4, 0, -2): # 오른쪽 특수 처리 result += 2 * li[j] # print(result) li.append(result+2) else: li.append(0) # if i % 2 == 0: # result = 0 # else: # li.append(0) # print(li) print(li[N])
시간복잡도
- O(n^2)
입력
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
4
11