[백준] 15990, 10844, 2193 (파이썬)

다이나믹 프로그래밍 문제를 계속 풀고있다. 이제 list를 1개만 이용하여 규칙성을 파악하는 것은 익숙해졌다. list를 2개 이용하는 경우에는 아직 가끔 막히는 느낌이 든다. 또한 메모리 초과에 대한 고려를 지금까지 하지 않아 이 부분에 대해서도 막혔었다. 그래도 점점 느는 것이 보여서 뿌듯한 느낌이다. 이 템포면 2주정도 뒤에는 1차로 목표하던 백준 골드티어에는 도달할 수 있을 것 같다.

백준 15990번 1, 2, 3 더하기 5

# 1차원적으로 생각하는 습관을 없애자
# 규칙성을 못찾아서 알고리즘 참고함
import sys
dp = [[0 for _ in range(3)] for _ in range(100001)]
dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]
for i in range(4, 100001):
    dp[i][0]=(dp[i-1][1]+dp[i-1][2])% 1000000009 # 나눠주지 않으면 메모리초과
    dp[i][1]=(dp[i-2][0]+dp[i-2][2])% 1000000009
    dp[i][2]=(dp[i-3][0]+dp[i-3][1])% 1000000009
T = int(sys.stdin.readline())
for j in range(T):
    n = int(sys.stdin.readline())
    print(sum(dp[n]) % 1000000009)

백준 10844번 쉬운 계단 수

import sys
dp = [[0 for _ in range(10)] for _ in range(101)]
# 각 자리수에서 맨 뒤에 올수 있는 숫자의 개수(0~9)
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, 101):
    dp[i][0]=(dp[i-1][1])%1000000000
    dp[i][1]=(dp[i-1][0]+dp[i-1][2])% 1000000000
    dp[i][2]=(dp[i-1][1]+dp[i-1][3])% 1000000000
    dp[i][3]=(dp[i-1][2]+dp[i-1][4])% 1000000000
    dp[i][4]=(dp[i-1][3]+dp[i-1][5])% 1000000000
    dp[i][5]=(dp[i-1][4]+dp[i-1][6])% 1000000000
    dp[i][6]=(dp[i-1][5]+dp[i-1][7])% 1000000000
    dp[i][7]=(dp[i-1][6]+dp[i-1][8])% 1000000000
    dp[i][8]=(dp[i-1][7]+dp[i-1][9])% 1000000000
    dp[i][9]=(dp[i-1][8])% 1000000000
N = int(sys.stdin.readline())
print(sum(dp[N]) % 1000000000)

백준 2193번 이친수

# 이정도 패턴은 이제 익숙해졌다.
import sys
dp = [1,1]
N = int(sys.stdin.readline())
for i in range(2, 91):
    dp.append(dp[i-2]+dp[i-1])
print(dp[N-1])