[백준🥈3] #11726 2xn 타일링 / #11727 2xn 타일링 2 (Python)

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로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

 

❌ Code (런타임 에러 - 인덱스 에러)

n = int(input())

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]

print(dp[n] % 10007)

문제점) n이 1일 경우, 즉 2x1을 타일링 할 경우 위의 코드처럼 짜면 dp[2]에서 인덱스에러가 발생하게 된다. 따라서 n이 1일 경우와 2일 경우 예외처리가 필요하므로 아래와 같이 코드를 수정하였다.

✔️ Code

n = int(input())

dp = [0] * (n+1)

for i in range(1, n+1):
    if i == 1:
        dp[i] = 1
        continue

    elif i == 2:
        dp[i] = 2
        continue

    dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)

 

✏️ Comment

규칙 : dp[i] = dp[i-1] + dp[i-2]

 

---

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

11727번: 2×n 타일링 2

 

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

 

✔️ Code

n = int(input())

dp = [0] * (n+1)

for i in range(1, n+1):
    if i == 1:
        dp[i] = 1
        continue

    elif i == 2:
        dp[i] = 3
        continue

    dp[i] = dp[i-1] + (dp[i-2]) * 2

print(dp[n] % 10007)

 

✏️ Comment

2xn 타일링에서 조금만 수정해주면 풀 수 있는 문제이다. 

2x1 -> 1개

2x2 -> 3개

2x3 -> 5개

2x4 -> 11개

여기까지는 구했는데, 규칙을 찾지 못했다.. 알고보니 규칙은 dp[i] = dp[i-1] + (dp[i-2]) * 2 .... ㅎㅎ