새싹프로그래머의 이야기

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

이번주 내내 solved.ac의 클래스 4에서 다이나믹 프로그래밍 문제를 3문제를 연달아 못풀었다..

그래서 당분간은 다이나믹 프로그래밍 문제를 풀어가며 해당 알고리즘을 공부해볼 생각이다.

문제:  2xn 타일이 주어졌을 때, 1x2 와 2x1 타일로 채울 수 있는 경우의 수를 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍으로 풀었습니다.

풀이 코드:

n = int(input())
dp = [0,1,2,3]



if n <= 3:
    print(dp[n])
else:
    for i in range(4,n+1):
        dp.append(dp[i-1] + dp[i-2])

    print(dp[n] % 10007)

풀이 설명:

n = 1일 때, 만들 수 있는 경우의 수는 1개 입니다.

n = 2일 때는, 2x1 타일로만 구성할 수도 있고 1x2 타일로만 구성할 수 있으므로 2개 입니다.

n = 3일 때는 3가지

n= 4일 때는 5가지

n = 5일 때는 8가지가 나오는 것을 알 수 있었습니다.

이를 바탕으로, 점화식 f(n) = f(n-1) + f(n-2)  ( n >= 3 ) 을 구할 수 있었고

이 점화식을 위 코드로 구현하여 문제를 해결하였습니다.