boj11726 2xn 타일링 (실버3) - DP

백준 문제 링크

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

11726번: 2×n 타일링

 

동적계획법(DP: Dynamic Programming) 

입력크기가 작은 부분의 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 큰 크기의 문제를 해결하는 방법.

 

n이 1일때, 2일때처럼 작은 문제들을 직접 해결한 후, 이후는 점화식을 세워서 재귀함수로 풀었음.

 

 

 

 

내 풀이

# boj11726 2xn 타일링 (실버3)
# DP 문제 (재귀 가능은 함)

# 재귀로 풀었을 때, RecursionError 발생. setrecurtionslimit을 설정해줘도 안됨.
# import sys
# sys.setrecursionlimit(10**6)
#
# def solution(n):
#     if n <= 3:
#         return n
#     return solution(n - 1) + solution(n - 2)
#
#
# n = int(sys.stdin.readline())
# print(solution(n) % 10007)



# DP(점화식)로 해결
import sys
n = int(sys.stdin.readline())
if n <= 2:
    print(n)
else:
    dp = [0 for i in range(n+1)]
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[n]%10007)

 

https://github.com/yj0903/python_CodingTest/blob/main/Algorithms/DP/boj11726.py

GitHub - yj0903/python_CodingTest: python_problemSolving