백준 10844번 - 쉬운 계단 수

첫 번째 자릿수가 1인 경우부터 9인 경우까지 계산을 해서 더하기엔 시간 초과가 뜰 것이 분명하다. 이전에 풀었던 RGB거리 문제를 생각해보면 i번째를 R로 칠한 값은 i-1번째를 G 혹은 B로 칠한 값 중에 작은 값에 R의 값을 더해주는 방식으로 최솟값을 갱신해주며 진행했다. 이 문제도 똑같은 방식으로 적용해보면, N번째 자릿수의 값이 각각 0~9일 때는 그 전인 N-1번째 자릿수까지의 경우들의 합일 것이다. 

 

##변수 선언 부분##
div_num = 10**9
data = []
sum = 0
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    data = [[0]*10 for x in range(N+1)]
    for i in range(1,10): #자리수가 1일 때는 1~9까지는 1로 초기화
        data[1][i] = 1

    for i in range(2,N+1): #1~N자리수까지
        data[i][0] = data[i-1][1] #0으로 끝나는 경우의 바로 전 시행은 1이다
        for j in range(1, 9): #1~8까지는 각각 두가지 경우가 있다
            data[i][j] = data[i-1][j-1] + data[i-1][j+1]
        data[i][9] = data[i-1][8] #9로 끝나는 경우의 바로 전 시행은 8이다

    for i in range(0,10):
        sum += data[N][i] #각 값들마다의 합을 구한다.

    print(sum%div_num)

동적 계획법 문제는 값을 갱신하면서 푸는 문제가 많은 것 같다.