문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
<코드>
def num_ways_to_tile(n):
if n == 1:
return 1
elif n == 2:
return 2
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = (dp[i-1] + dp[i-2]) % 10007
return dp[n]
n = int(input())
print(num_ways_to_tile(n))
<풀이과정>
- DP 배열 정의:
- dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수라고 정의
- 점화식:
- 2×n 크기의 직사각형을 채우는 방법의 두 가지 경우:
- 마지막에 2×1 타일 하나를 세로로 놓는 경우: 남은 공간은 2×(n-1) 크기. 즉, 이 경우는 dp[n-1]에 해당
- 마지막에 1×2 타일 두 개를 가로로 놓는 경우: 남은 공간은 2×(n-2) 크기. 즉, 이 경우는 dp[n-2]에 해당
- 점화식: dp[n]=dp[n−1]+dp[n−2]
- 2×n 크기의 직사각형을 채우는 방법의 두 가지 경우:
- 초기값 설정:
- dp[1] = 1: 2×1 크기의 직사각형을 채우는 방법은 1가지
- dp[2] = 2: 2×2 크기의 직사각형을 채우는 방법은 2가지 (2×1 타일 두 개 또는 1×2 타일 두 개)
- 결과 계산:
- 최종 결과를 10,007로 나눈 나머지를 출력해야 하므로, 각 DP 값을 계산할 때마다 10,007로 나눈 나머지 구하기
'2024 코딩테스트 스터디' 카테고리의 다른 글
[13주_7일차] 백준-11066 파일 합치기(Python) (0) | 2024.09.02 |
---|---|
[13주_5일차] 백준-11722 가장 긴 감소하는 부분 수열(Python) (0) | 2024.09.01 |
[13주_4일차] 백준-15486 퇴사2(Python) (0) | 2024.08.30 |
[13주_3일차] 프로그래머스-등굣길(Python) (0) | 2024.08.29 |
[13주_2일차] 프로그래머스-정수 삼각형(Python) (0) | 2024.08.28 |