백준 11726번 2xn 타일링 [Python]

[Silver III] 2×n 타일링 - 11726

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 3월 26일 09:31:17

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

DP를 이용한 문제이다. DP는 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. 2xn크기의 직사각형을 채우는 방법의 수를 구하기 위해서는 2*(n-1)크기의 방법의 수 + 2*(n-2)크기의 방법의 수 이 식을 적용해야 한다.

n = int(input())

dp = [0]*1001

dp[1] = 1 # 2x1크기의 직사각형 채우는 방법의 수 == 1
dp[2] = 2 # 2x2크기의 직사각형 채우는 방법의 수 == 2

먼저 정수 n을 입력받는다. 그리고 n의 범위가 (1 ≤ n ≤ 1,000)이므로, dp 리스트의 크기를 1001만큼 0으로 초기화한다. 1001로 하는 이유는 인덱스 0을 쓰지않고 1부터 1000까지 쓰기위함이다. 그리고 1의 경우와 2의 경우 dp의 초기값을 저장한다.

for i in range(3, n+1): # dp[1]과 dp[2]를 이용해 3부터 n까지 이전 값들을 이용해서 연산을 반복
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%10007)

위에서 지정한 1의 경우와 2의 경우를 이용해서 3부터 n까지 누적해서 그 합을 저장한다. 이전의 값을 이용함으로써 연산속도를 증가시켜준다. 반복문이 끝난 이후에는 10007로 나눈 나머지 값을 출력시킨다.

전체코드

import sys

input = sys.stdin.readline

n = int(input())

dp = [0]*1001

dp[1] = 1
dp[2] = 2

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%10007)