조건을 만족하는 숫자의 개수를 구하는 문제이다.

Why DP?

자리수가 하나씩 증가하기 때문에
i자리 숫자의 개수와 i+1자리 숫자의 개수가 연관이 있을 수 밖에없다. 여기서 dp라는 포인트를 잡아야 한다.

연관이 있는거같긴한데 계단수를 직접 써봐도 dp 변수와의 연관성을 찾기 쉽지 않았다. 풀이를 살펴보니 1차원 dp만 생각해서 그런 것이었다.

몇 자리수인지에 추가해서 무슨수로 끝나는지도 중요한 정보이기때문이다.

Correct

dp[자릿수][끝나는수] = 조건을 만족하는 경우의 수

즉, dp[3][2] = 3자리수 중에 2로 끝나느 조건을 만족하는 수의 경우의 수 ex) 432 ..

초기값 세팅

dp[1][1]~dp[1][9] = 1이다.

점화식

dp[i][0] = dp[i-1][1] , 0으로 끝나기 위해선 1로 끝난 수의 0이 붙는 경우의수만 존재한다.

dp[i][9] = dp[i-1][8], 9로 끝나기 위해선 8로 끝난 수의 +1 하는 방법밖에 존재하지 않는다.

dp[i][j] = dp[i-1][j+1] + dp[i-1][j-1], 그 중간 수는 j가 되기위해 +1하거나 -1할 수 있다.

코드

n = int(input())

dp = [[0]*10 for _ in range(n+1)]

for i in range(1,10):
    dp[1][i] = 1


for i in range(2,n+1):
    for j in range(0,10):
        if j == 0:
            dp[i][0] = dp[i-1][1]
        elif j == 9:
            dp[i][9] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[n]) % (10**9))

문제의 핵심

연관성과 dp 변수로의 관계를 점화식으로 나타내기 힘들땐 핵심 변수를 생각하고 dp 차원을 늘려야 한다.