백준 11057 - 오르막 수 (Python3)

코드

n = int(input())

# d[1~9까지 끝자리에 오는 수][n : 자리 수]
# 1001 : n의 최대 범위
d = [[1 for _ in range(10)] for _ in range(1001)]

# 로직 구현
def solution(n):
    
    # 1인 경우 무조건 10개
    if n == 1:
        return 10
    
    for i in range(2, n+1):
        for j in range(10):
            
            # j가 0 : 끝이 0으로 끝나는 경우는 무조건 1개
            # ex : n == 2 => 00, n == 3 => 000
            if j == 0:
                d[i][j] = 1
                
            # 0이 아닌 경우
            # 같은 길이 n에 끝자리 수가 -1인 경우
            # +
            # n-1의 길이에 끝자리 수가 같은 경우
            else:
                d[i][j] = d[i-1][j] + d[i][j-1]

    # n 전체 합을 % 10007로 나누면 정답
    return (sum(d[n]) % 10007)
     
print(solution(n))

문제 해설

DP 문제.

쉬운 계단 수

위 링크의 문제와 매우 유사한 문제.

위의 그림을 보면 알 수 있듯이 DP 테이블의 점화식을 구하는 것은 생각보다 어렵지 않았다. n이 1 인 경우와, 끝자리 수가 0인 경우에 대해서만 별도 처리를 해주면 별다른 어려움 없이 풀 수 있었다.