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

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

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

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

11726번: 2×n 타일링

 

풀이

점화식을 사용하는 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 로 나눈 나머지를 출력하는 것을 제대로 읽지 않아 틀린것은 안비밀