[파이썬] 백준 11726 : 2xn 타일링 (python)

* 체크 리스트

---

시간

1. 즉시 작성 가능
2. 1시간 이내
3. 1시간 이상
4. 하루 이상

이해도

1. 이해 완료
2. 복습 필요
3. 부분 이해
4. 이해 불가

체감 난이도

1. 최상
2. 상
3. 중
4. 하
5. 최하

---

문제

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

입력

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

출력

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

---

핵심 풀이

다이나믹 프로그래밍(DP)의 풀이의 핵심은 '규칙'을 찾아야 한다.

위 그림을 보면 1x2크기의 직사각형을 2xN 크기의 직사각형에 직접 대입해 보았다.

2X1	2X2	2X3	2X4	2X5
1개	2개	3개	5개	8개

표와 같이 1,2,3,5,8개로 일정한 규칙이 있다. 즉, 1+2 = 3 / 2+3 = 5 / 3+5 = 8인데, 이를 식으로 나타내면

d(n) = d(n-1)+d(n-2)

로써 표현이 가능.

---

풀이 1 - 오답

N = int(input())


def data(N):
    if N == 1:
        return 1
    if N == 2:
        return 2
    return data(N-1)+data(N-2)


print(data(N) % 10007)

재귀 함수를 활용하여 코드를 풀어보려 했지만, 무한루프에 가까운 비효율의 극치이다. - 런타임 에러

풀이 2 - 반복문 사용

N = int(input())
# 1부터 N까지 숫자를 리스트에 넣는다.
res = [i+1 for i in range(N)]
# 2이하의 숫자는 그대로 출력한다.(규칙 없음)
if N <= 2:
    print(N)
else:
    # 3부터 N까지 규칙에 맞춰 대입한다.
    for i in range(3, N):
        res[i] = res[i-1]+res[i-2]
    print(res[N-1] % 10007)

규칙이 없는 2 이하의 숫자는 그대로 출력한다.

그 외의 수는 d(n) = d(n-1)+d(n-2) 규칙을 활용하여 해결함.

출처

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

11726번: 2×n 타일링

깃 주소

https://github.com/justin-kim3000/Python_Algorithm/blob/main/DynamicProgramming/2xN(11726).py 

GitHub - justin-kim3000/Python_Algorithm: Study