[모각코_06] 알고리즘 공부_4

백준으로 알고리즘 공부 (파이썬)

 

일시 및 장소: 8/14(일) 20:00~23:00 Discord

 

 

문제:

코드: 

n = int(input())

dp = [0]*1001
dp[1] = 1
dp[2] = 2

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


print(dp[n]%10007)

2xn 크기의 직사각형을 채우는 방법은 2x(n-1)까지 채우고 세로로 직사각형 하나를 더해서 채우는 방법과

2x(n-2)까지 채우고 가로로 직사각형 두개를 더해서 채우는 방법이 있다. 

따라서  2x(n-1)까지 채우는 방법의 수와 2x(n-2)까지 채우는 방법의 수를 더하면 된다.

 

 

소감:

처음에 시작 방향을 잘못 잡아서 조금 헤맸었는데 동적 계획법을 이용해서 푸는 것이라는 걸 알고나서는 쉽게 풀 수 있었다. 이 문제가 시간이 제일 많이 걸렸다. 이번 방학때 모각코를 하면서 xpdf puzzing하는 방법도 배우고 알고리즘 공부와 파이썬 공부를 같이 할 수 있어서 좋았다. 유익한 방학을 보낸것 같다.