[Code Tree] 사각형 채우기 3 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-rectangle-fill-3/description

사각형 채우기 3 설명 | 코드트리

 

---

풀이

문제 요약

2 * N 크기의 사각형에 1 * 2, 2 * 1, 1 * 1 크기의 사각형으로 채우는 방법의 수를 구하자.

아이디어

점화식은 다음과 같다.

dp[i] : 2 * i 크기 사각형을 채우는 방법의 수

1*1 사각형으로 인해 변수가 많아졌다. 하나씩 살펴보자.

dp[1]은 21 한 개와, 11 두 개로 만들 수 있다.(dp[1] = 2)

dp[2]는 예제에서 주어진 것처럼 총 7가지 방법이 가능하다. (dp[2] = 7)

N ≥ 3에 대해서는 다음이 성립한다.

• dp[i - 1]에 21 한 개 또는 11 두 개를 붙이는 방법
• dp[i - 2]에 12 두 개 또는 12 한 개와 1*1 두 개를 붙이는 두 가지 방법이 있다.
• dp[i - 3]에 대해 21을 i개, 11 두 개를 붙이는 두 가지 방법이 있다.

이때, i가 늘어남에 따라, i - 3. i - 4번째 dp 누적합 경우의 수에 비례한다.

따라서 dp의 누적합을 따로 구해주며 점화식을 완성시키자.

dp[i] = 2dp[i - 1] + 3dp[i - 2] + 2*sum_dp[i - 3]

수가 너무 커질 수 있으니, 1e9 + 7로 나눈 나머지를 출력하자.

n = int(input())

# Please write your code here.

def solve(N):
    if N == 1:
        return 2
    if N == 2:
        return 7
    
    MOD = int(1e9) + 7
    dp = [0] * (N + 1)
    sum_dp = [0] * (N + 1)
    dp[1] = 2
    dp[2] = 7
    sum_dp[0] = 1
    sum_dp[1] = sum_dp[0] + dp[1]
    sum_dp[2] = sum_dp[1] + dp[2]
    for i in range(3, N + 1):
        dp[i] = (2*dp[i - 1] + 3*dp[i - 2] + 2*sum_dp[i - 3]) % MOD
        sum_dp[i] = (sum_dp[i - 1] + dp[i]) % MOD
    return dp[N]

print(solve(n))

풀이 시간

20분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/04 사각형 채우기 3(challenge-rectangle-fill-3).py

problem-solving/code-tree/Algorithm Intro/DP I/04 사각형 채우기 3(challenge-rectangle-fill-3).py at main · rogi-rogi/prob