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

제한 사항

문제

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

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

입력

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

출력

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

예제

 

---

나의 풀이

2021.09.20 - [solved.ac 실버3] 2xn 타일링 (DP 풀이)

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

위 문제와 완전히 동일한 풀이이다. 위 글에 자세히 설명했으니 참고 바람.

다만 i-2번째 위치에서 경우의 수가 가로 타일을 2개 추가하는 경우와 2x2 타일을 하나 추가하는 경우 이렇게 2개의 경우가 되었다는 점만 다르다.

즉, i-2 위치의 값에서 2를 곱하기만 하면 된다.

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

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

혹은

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

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

 

채점 결과