[solved.ac 실버3] 11726_2xn 타일링 (DP 풀이)

제한 사항

문제

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

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

입력

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

출력

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

예제

 

---

나의 풀이

전형적인 DP 문제이다.

우리는 블록을 채우는 경우가 다음 2가지 경우 밖에 없다는 사실을 깨달아야 한다.

세로 타일

가로 타일 2개

세로 타일을 2개 연속 세워서 2x2 블록을 만들 수 있지 않냐고 생각할 수 있다. 헷갈린다면 일단 설명을 계속 읽어보자.

 

i번째 위치에서 타일로 채우는 방법 수를 구하려면 2가지를 더하면 된다.

• i-1번째까지의 블록에서 세로 타일을 추가하는 방법
• i-2번째까지의 블록에서 가로 타일을 2개 추가하는 방법

DP로 풀이할 수 있는 이유가 위와 같다. 일반화를 할 수 있는 것이다.

DP 테이블의 i번째 위치에는 i번째 블록까지 쌓을 수 있는 방법 수가 저장된다.

 

이 사실을 기억하고 위에서 궁금했던 세로 타일을 2개 연속 세우는 경우를 세지 않는 이유를 생각해보자.

만약 i번째 블록까지 쌓는데 가능한 경우의 수를 구한다고 했을 때 우선 i-1번째까지의 블록에 세로 타일을 하나 추가하는 방법이 있을 것이고,

i-2번째까지의 블록에 가로 타일 2개를 추가하는 방법이 있을 것이다. 

만약 우리의 궁금증 처럼 세로 타일 2개를 추가해서 2x2 블록을 만드는 경우는 위 그림과 같을 것이다.

하지만 이는 중복이 된다. i-1번째까지의 경우의 수에서 세로 블록 하나만 추가한 경우와 i번째까지의 경우의 수에서 세로 블록 2개를 추가하는 경우는 중복으로 세게 된다.

이 정도 설명하면 될 것 같다. 중복되지 않게 세는 것이 중요하다.

---

어쨌든 결론은 d[i] 번째 값은 d[i-2] + d[i-1] 이다.

 

전체코드

def solution(n):
    if n == 1: return 1
    d = [0] * (n+1)
    d[1], d[2] = 1, 2
    for i in range(3, n+1):
        d[i] = (d[i-2] + d[i-1]) % 10007
    return d[n]

n = int(input())
print(solution(n))

물론 가로 한 칸짜리를 세우는 방법은 세로 타일 하나만 사용하는 1가지이다.

def solution(n):
    d = [0] * (n+1)
    d[0], d[1] = 1, 1
    for i in range(2, n+1):
        d[i] = (d[i-2] + d[i-1]) % 10007
    return d[n]

n = int(input())
print(solution(n))

이렇게로도 변경할 수 있다.  가로가 0인 블록을 만드려면 아무것도 안 세우는 한 가지 방법이 있으니 의미가 통한다.

채점 결과