[알고리즘-DP] 백준 10844번 문제풀이

백준 10844번 문제풀이

1. n 입력 받기

2. dp 초기 배열 생성하기.
1. [0]이 10개씩 n+1만큼 있음.
2. 한 칸에 올 수 있는 숫자가 10개이고, 상자가 n+1의 크기이기 때문이다.
3. dp[n자리][마지막 자리의 수]

3. 그리고 크기가 1인 초기 형태를 초기화한다.
1. 크기가 1일 때는 1~9의 수가 모두 한 번 씩 올 수 있다. 0은 못 온다.

4. 크기가 2인 경우부터는 점화식을 이용해서 케이스별로 구현한다.
1. 앞자리가 0인 경우에는, 뒷자리에 1만 올 수 있다
2. 앞자리가 9인 경우에는, 뒷자리에 8이 올 수 이따
3. 앞자리가 1~8인 경우에는, (앞자리 수를 j라고 두면) 뒷자리에 j-1와 j+1 두 수가 올 수 있다.

5. 문제 요구사항에 따라 1000000000의 나머지를 출력

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(10):
        if j==0:
            dp[i][j]=dp[i-1][1]
        elif j==9:
            dp[i][j]=dp[i-1][8]
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
print(sum(dp[n])% 1000000000)