Notice
Recent Posts
Recent Comments
Link
꾸준하게 거북이처럼
백준 2133번 파이썬 본문
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
풀이
n이 홀수일 때는 1x2, 2x1로 3xn 모양의 타일을 만들 수 없다.
짝수 일 때의 경우를 그려보면 위와 같은데,
n이 4부터는 이전의 타일( d[2]와 d[2]를 가지고 만듦)을 이용해서 만드는 것뿐만 아니라 좀 새로운 모양의 타일이 2개씩 생긴다.
n이 6일 때는 dp[4] * dp[2] + dp[2] * dp[4]의 새로운 모양타일 2개 + dp[6]에서 만들어진 새로운 모양 타일 2개
....
dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + ..... + dp[0] * 2
와 같은 점화식을 구할 수 있다.
코드
dp = [0] * 31
dp[0] = 1
dp[2] = 3
n = int(input())
if n % 2 != 0:
print(0)
else:
if n == 2:
print(3)
else:
for i in range(4, n + 1, 2):
for j in range(2, i + 1, 2):
if j == 2:
dp[i] += dp[i - j] * 3
else:
dp[i] += dp[i - j] * 2
print(dp[n])
참고자료
[백준] 2133: 타일 채우기 파이썬 리뷰
2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이는 블로그 1, 블로그 2 를 참고했습니다. d(i-4) * 2 + ... + d(0) * 2 부분이 이해하기 힘..
ahn3330.tistory.com
'Algorithm 문제 & 공부 > DP' 카테고리의 다른 글
| 프로그래머스 - 전력망 둘로 나누기 js (1) | 2023.12.06 |
|---|---|
| 백준 13398번 파이썬 - 연속합2 (0) | 2022.08.26 |
| 백준 11054번 파이썬 - 가장 긴 바이토닉 부분 수열 (0) | 2022.08.25 |
| 백준 11055번 파이썬 (0) | 2022.08.23 |
| 백준 2156번 - 파이썬 (1) | 2022.08.21 |
Comments