몽상실현개발주의

[BOJ] 11726 / 2×n 타일링 / Python 본문

Algorithm PS/BOJ

[BOJ] 11726 / 2×n 타일링 / Python

migrationArc 2021. 5. 9. 19:17

[BOJ] 11726 / 2×n 타일링 / Python

[BOJ] 11726 / 2×n 타일링 / Python

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

 

풀이

점화식을 사용하는 dp 문제 였다.

N = 1 -> 1
N = 2 -> 2
N = 3 -> 3
N = 4 -> 5
N = 5 -> 8
N = 6 -> 13

경우의 수를 구해보니 점화식이 피보나치 수열과 같다는 것을 알 수 있었다.

dp(N) = dp(N-1) + dp(N-2)

 

그래서 처음에는 재귀함수를 이용하여 시도 하였다.

N = int(input())

def solution(N):
    if N == 1:
        return 1
    if N == 2:
        return 2
    
    return solution(N-1)+solution(N-2)

print(solution(N))

결과는 Recursion Error.

 

그래서 두번째 방법으로 Tabulation 으로 시도 하였다.

N = int(input())

dp = [0, 1, 2] + [0]*N

for i in range(3, N+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[N]%10007)

문제 없이 통과.

 

※ 출력 조건인 10007 로 나눈 나머지를 출력하는 것을 제대로 읽지 않아 틀린것은 안비밀

Comments