https://www.acmicpc.net/problem/11726
문제 분석
- 2xn 크기의 직사각형을 2x1, 1x2 타일로 채우는 방법의 수 % 10007 출력
풀이
완탐 - 시간초과
- n을 1과 2의 합이 되는 중복순열의 수 (순서o, 중복o)
- 조합 : product
dp
- 이전에 계산한 것들을 저장
- dp[i] = 2 x i 크기의 타일에 들어갈 경우의 수
- dp[1] : 1가지 [1]
- dp[2] : 2가지 [(1,1), 2]
- dp[3] : 3가지 [(1,1,1), (1,2), (2,1)]
- dp[4] : 5가지 [(1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)]
- I가 짝수이면 이전에 대해 +1
- i가 홀수이면 이전에 대해 +2
정답 코드
1. 시간초과 : 완탐
import sys
input = sys.stdin.readline
from itertools import product
n = int(input())
arr = [1,2]
cnt = 0
for i in range(n+1) :
for j in product(arr, repeat=i) :
if sum(list(j)) == n :
cnt += 1
print(cnt)
2. dp - 점화식
import sys
input = sys.stdin.readline
n = int(input())
dp = [0 for _ in range(n+1)]
if n >= 1 :
dp[1] = 1
if n >= 2 :
dp[2] = 2
if n >= 3 :
for i in range(3, n+1) :
dp[i] = dp[i-1] + dp[i-2]
print(dp[n] % 10007)
'코딩 테스트 > 백준' 카테고리의 다른 글
[Python] 백준 2293 동전 1 (0) | 2025.04.23 |
---|---|
[Python] 백준 1655 가운데를 말해요 (0) | 2025.04.22 |
[Python] 백준 2941 크로아티아 알파벳 (0) | 2025.04.20 |
[Python] 백준 2294 동전 2 (0) | 2025.04.17 |
[Python] 백준 1261 알고스팟 (0) | 2025.04.15 |