[PS][BOJ/14852번]-타일 채우기3

문제 설명

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

입력

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

출력

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

문제 분석 과정

주어진 조각은 3개이고, 회전은 불가능하다

마지막 칸(가장 우측)을 바라 보자 그러면 가능한 마지막칸을 구성하기
위한 case를 나눌 수 있다.

1. 1x1을 2개를 구성해서 2x1칸을 이루는 경우 => (2,1)
2. 2x1 1개로 2x1칸을 이루는 경우 => (1,1)+(1,1)
3. 1x2 1개로 2x2칸을 이루는 경우 => (1,2)+(1,2)
4. 1x1개로 위에 한칸을 이루는 경우 => (1,1)
5. 1x1개로 아래에 한칸을 이루는 경우 => (1,1)

n일때의 솔루션을 구하는 문제가 위 Case를 통해서 쪼개질 수 있다.

How?

n의 솔루션을 구하는 문제 = dp(n) 이라고 한다 하면
n 번째에서의 Case로 나눠서 생각할 수 있다.
예를들어, 2번 케이스를 살펴보자.2번케이스일 때, n까지의 솔루션을 구하는 문제를 n-1까지의 솔루션을 구하는 문제로 생각할 수있다.
그럼 dp(n)을 표현할 때 dp(n-1)과 다른 점화식으로 표현할 수 있다
이와 같은 논리로 1~3번 Case 까지를 dp(n)을 표현하면
dp(n) = dp(n-1) + dp(n-1) + dp(n-2) 으로 표현 할 수 있다.

남은 두가지 케이스를 살펴보자
Case 4와 Case 5 유사하므로 Case 4 만 완전히 이해하면된다.

위의한칸으로 인한ㄴ자 모양이 생긴다 이 ㄴ자 모양에 주목 해야한다.
ㄴ 자 모양의 윗 부분은 n-1개의 타일, 아랫 부분은 n개의 타일로 구성된다.
이 경우를 A(n-1) 이라고 정의하자

A(n) 을 그림으로 간단하게 표현하면 다음과 같다.

n개
ㅁㅁㅁㅁ
ㅁㅁㅁ
n-1개

B(n) 을 그림으로 간단하게 표현하면 다음과 같다.

n-1개
ㅁㅁㅁ
ㅁㅁㅁㅁ
n개

A(n-1)을 구성하는 점화식을 찾은 다음 dp(n)을 분해했던 것 처럼 Case를 나눌 수 있다

이러한 과정을 거치면 아래와 같은 점화식을 얻을 수 있다.

점화식

dp(n) = dp(n-1) + dp(n-1) + dp(n-2) + A(n-1) + B(n-1)

A(n-1) = dp(n-2) + B(n-2)

B(n-1) = dp(n-2) + A(n-2)

소스코드

import sys
input = sys.stdin.readline
# A(1)
# ㅁ
# 

# A(2)
# ㅁㅁ
# ㅁ

# 점화식
#       (2,1), (1,1)+(1,1) , (1,2)+(1,2) , (1,1)+(1,2) ,(1,2)+(1,1)
# dp(n) = dp(n-1) + dp(n-1) + dp(n-2) + A(n-1) + B(n-1)

# A(n-1) = dp(n-2) + B(n-2)
# B(n-1) = dp(n-2) + A(n-2)

# 입력받기 
n = int(input())

# 초기화
dp = [0]*(n+2)
A = [0]*(n+2)
B = [0]*(n+2)

dp[1] = 2
A[1] = 1
B[1] = 1

dp[2] = dp[1]*2 + 1 + A[1] +B[1]

if n > 2:
    # 초기화 (기본 값)/ 바텀업 방식
    for i in range(3,n+1):
        B[i-1] = dp[i-2] + A[i-2]
        A[i-1] = dp[i-2] +B[i-2]
        # 메모리 초과 나왔었음 % 연산 분배 법칙으로 메모리 절약 
        dp[i] = (dp[i-1]*2 +dp[i-2] + A[i-1] +B[i-1])%1000000007
    
    print(dp[n])

else:
    print(dp[n]%1000000007)

문제 원본
소스코드 원본

오류나 질문에 대한 문의 댓글로 남겨주겨주세요!