백준 알고리즘 | 11726 : 2 x n 타일링 (Python / 파이썬)

---

2×n 타일링 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	69818	25756	18856	34.635%

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

문제

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

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

​

입력

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

​

출력

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

알고리즘 분류

다이나믹 프로그래밍

---

 

백준 알고리즘 # 11726번 : 2 x n 타일링

n = int(input())

# [0, 0, 0, 0 ...]
dp = [0 for _ in range(n + 1)]

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

    print(dp[i] % 10007)

풀이

key point 1

먼저 점화식을 찾아내자면, 2x5 크기의 직사각형이 5개로 이루어져있니 나열하면

1, 2, 3, 5, 8, 13 ... 식으로 n의 앞에 있는 n-1과 n-2를 더해주는 점화식(규칙)을 찾을 수 있어요👏🏻

​

다음으로 n을 변수로 값을 입력받고, dp 리스트를 만들어준 뒤

​

key point 2

3 이하의 수는 1x2로도 모두 표현할 수 있으니 n을 그대로 받아줬습니다.

​

때문에 if문과 else문 모두 1, 2일 때는 n이 그대로 나오게끔 코드를 짰고

else문에서 for 반복문으로 3부터 n+1까지는 i를 인수로 받아서 점화식을 이용해서 답을 구해봤어요🙌🏻

​

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

10,007을 나눈 나머지를 출력하면 문제 풀이 끄-읏!👊🏻

​

자세한 코드가 궁금하신 분들은 아래 GitHub 코드를 참고해주세요🙏🏻

wook2124/Algorithm-Test

최종 소스코드