2019.02.22) 백준 11726번, 11727번 풀이 (PyPy3)

이런 류의 문제를 어떻게 접근할지 몰랐는데 찾아보니 점화식으로 하면 된다더라.

그래도 이해가 안되서 5번째까지 직접 써보니 이해가 됐다.

11726번

a = int(input())
 
# 점화식은 a[n] = a[n - 1] + a[n - 2] 이다
# 하지만 피보나치 수열과 다르게 시작은 1번쨰부터 1, 2로 시작한다
# 새로 놓여질 블럭이 세로로 세워지면 a[n - 1]의 경우의수,
# 새로 놓여질 블럭이 앞에 블럭과 가로로 세워지면 2칸 전인 a[n - 2]의 경우의수를 가진다.
dp = [0, 1, 2]
 
for i in range(2, a):
    dp.append((dp[i] + dp[i-1]) % 10007)
 
print(dp[a])
 
 
 

11727번

a = int(input())
 
# 점화식은 a[n] = a[n - 1] + a[n - 2] * 2 이다
# 새로 놓여질 블럭이 세로로 세워지면 a[n - 1]의 경우의수,
# 새로 놓여질 블럭이 앞에 블럭과 가로로 세워지면 2칸 전인 a[n - 2]의 경우의수,
# 새로 놓여질 블럭이 앞에 블럭 합쳐져 2x2가 된다면 2칸 전인 a[n - 2]의 경우의수가 된다.
dp = [0, 1, 3, 5]
 
for i in range(3, a):
    dp.append((dp[i] + dp[i-1] * 2) % 10007)
 
print(dp[a])