[BOJ][🟡4][백준#14852] 타일 채우기 3

문제 출처

BAEKJOON Online Judge #14852

문제

2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.

입력

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

출력

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제

예제 1

입력

1

출력

2

예제 2

입력

2

출력

7

예제 3

입력

3

출력

22

My Sol

def main():
    M = 1000000007
    ans = [0, 2, 7]
    N = int(input())
    if N < 3: return ans[N]

    cnt, cross = 2, 1
    a, b, c = ans
    while cnt < N:
        new_c = (2*cross+3*b+2*c)%M
        a, b, c = b, c, new_c
        cnt += 1
        cross += a
        cross %= M

    return c

print(main())

DP를 활용해 푸는 문제였다.

문제 풀이의 관건은 dp[N-3] ~ dp[1] 영역처럼 교차해서 반복되는 것이다. 이는 2가지씩 이고, dp[N-3] 부터 dp[1] 까지 개수에 2배씩 하여 경우의 수를 계산해주어야 한다.

또한 또다른 노하우는 모든 dp 배열을 저장하는 것이 아닌, pythonic하게 변수 3개로 이전 값을 미루며 저장, 갱신하여 풀어낸 것이다.

new_c = (2*cross+3*b+2*c)%M
a, b, c = b, c, new_c

결과

맞았습니다!!