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

문제

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

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

 

---

풀이

문제 요약

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

아이디어

점화식은 다음과 같다.

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

2 * N을 채우기 위해서는 dp[i - 1]에 2 * 1 사각형 한 개를 붙이는 경우,

dp[i - 2]에 12 사각형 두 개를 붙이거나, 22 한개를 붙이는 경우가 존재한다.

따라서 N ≥ 3에 대해 dp[i] = dp[i - 1] + 2 * dp[i - 2]가 성립한다.

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

n = int(input())

# Please write your code here.

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

print(solve(n))

풀이시간

5분

---

소스코드

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

problem-solving/code-tree/Algorithm Intro/DP I/06 사각형 채우기 2(test-rectangle-fill-2).py at main · rogi-rogi/problem-s