[Python/코테] 백준 11726 2xn 타일링

11726 2xn 타일링

문제 및 조건 설명: https://www.acmicpc.net/problem/11726

알고리즘 설계

1. 테이블 정의하기

D[i] = 2 x i 크기의 직사각형을 채우는 방법의 수

 

2. 점화식 찾기 

2 x n일 때 가장 왼쪽 위의 타일을 채우는 방법

1) 2x1로 채운다.

2x(n-1) 칸이 남았으므로 나머지 칸을 채우는 방법의 수는 D[n-1]이다.

 

 

2) 1x2로 채운다.

아래에 1x2로 채우는 경우가 유일하므로 2x(n-2) 칸이 남게 된다.

 나머지 칸을 채우는 방법의 수는 D[n-2]이다.

 

즉 D[n] = D[n-1] + D[n-2]

 

3. 초기값 지정하기

D[1] = 1
D[2] = 2

알고리즘 구현

✔️ 모든 결과를 계산하고 출력에 맞춰 나머지 연산을 하면 int overflow (C++에서) 발생할 수도 있다. 중간 중간 계속 나머지 연산을 수행해서 나머지만을 가져가야 한다.

n = int(input())
d = [0] * 1001


def func():
    if n == 1:
        print(1)
        return

    d[1] = 1
    d[2] = 2

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

    print(d[n])


func()

나다어

• 모든 경우의 수를 구해야 할 때, 한 번에 모든 경우를 생각해낼 수 없으니 경우를 나눠서 생각하자. (사실상 그 DP의 정의이자 핵심이지만..)