2019.02.25) 백준 11057번, 2193번 풀이 (PyPy3)

dp가 재밌어서 은근 많이 했는데 이제 슬슬 그만두고 다음부턴 lcs lis를 공부해볼까 한다.

11057번

a = int(input())
 
# dp용 배열
dp = [None, [1 for i in range(10)]]
 
for i in range(2, a + 1):
    # 높은 index의 값을 다 더해서 저장
    dp.append([sum(dp[i - 1][z:]) for z in range(10)])
 
print(sum(dp[a]) % 10007)

2193번

a = int(input())
 
# dp용 배열
dp = [None, [1, 1]]
 
for i in range(2, a + 1):
    # 0으로 시작할떈 다음에 1로시작해도 되고 0으로 시작하도 되고
    # 1로 시작할땐 0으로만 시작해야함
    dp.append([sum(dp[i - 1]), dp[i - 1][0]])
 
# 이친수는 1로 시작하므로 1번쨰 배열값만 출력
print(dp[a][1])