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

문제

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

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

 

---

풀이

문제 요약

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

아이디어

점화식은 다음과 같다.

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

2 * i 크기의 사각형을 채우기 위한 방법은 2 * (i - 1) 사각형에 2 * 1 사각형 하나를 붙이는 경우와, 2 * (i - 2) 사각형에 1 * 2 사각형 두개를 붙이는 방법이 있다.

따라서 dp[i] = dp[i - 1] + dp[i - 2]가 성립한다.

• dp[1] = 1
• dp[2] = 2
• dp[i] = dp[i - 1] + dp[i - 2] { N ≥ 2 }

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

n = int(input())

# Please write your code here.

def solve(N):
    if N <= 2:
        return N
    
    MOD = int(1e4) + 7
    dp = [0] * (N + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, N + 1):
        dp[i] = (dp[i - 1] + 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/03 사각형 채우기(challenge-rectangle-fill).py

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