[백준11726번][백준][baekjoon][11726번][DynamicProgramming][DP][2xn타일링][Python][파이썬]

문제링크

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제

 

풀이

이번 문제 역시 DP로 풀기 좋은 문제입니다. 2xn 크기의 직사각형을 1x2 도형과 2x1도형을 사용하여 채우는 방법의 경우의 수를 구하는 문제입니다. 염두하여야 할 것은, 2xn 직사각형을 채울 때 2x1크기의 도형은 계속해서 쌓을 수 있지만 1x2크기의 도형은 두 개가 합쳐질 경우 2x2도형으로 만들어 쌓아야 하는 것입니다. 점화식을 유도하기 앞서 경우를 나열해보겠습니다. 설명의 편의를 위해 1x2 도형은 l로, 2x1 도형은 = 으로 표시하겠습니다.

 

2x1 직사각형 : l    (1 가지)

2x2 직사각형 : ll, = (2 가지)

2x3 직사각형 : lll, =l, l= (3 가지)

2x4 직사각형 : llll, =ll, l=l, ll=, == (5 가지)

2x5 직사각형 : lllll, =lll, l=ll, ll=l, ==l, lll=, =l=, l== (8 가지)

 

위의 경우의 수를 단순하게 생각해서, 2xn 직사각형은 2x(n-1) 직사각형의 경우의 수와 2x(n-2) 직사각형의 경우의 수를 합한 결과로 나옵니다. 급할때는 이렇게 풀어도 되겠지만 이 이유를 설명하면 다음과 같습니다. 2x5 직사각형을 채우는 경우는 2x4 직사각형을 채우는 경우(5 가지)에서 각각 1x2 도형을 채우는 경우, 2x3 직사각형을 채우는 경우(3 가지)에서 각각 2x2 도형을 채우는 경우의 합으로 표시됩니다. 이해를 돕기 위해 위의 나열된 경우에서 순서대로 나열하였습니다. 새로운 도형을 추가시기는 방법이 1x2 도형을 추가하는 방법과 2x2 도형을 추가하는 방법 두 가지가 존재하기 때문에 이러한 결과를 나타냅니다. 이를 점화식으로 나타내면 다음과 같습니다.

 

D[N]=D[N-1]+D[N-2]

 

소스코드

#Python

testcase=int(input())
 
dp=[0 for _ in range(10001)]
 
for i in range(1, testcase+1):
    if i==1:
        dp[i]=1
    elif i==2:
        dp[i]=2
    else:
        dp[i]=dp[i-2]+dp[i-1]
print(dp[testcase]%10007)

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.