[DP] 10844번 쉬운 계단 수

https://www.acmicpc.net/problem/10844

알고리즘

• Dynamic Programming

풀이

포인트

• 계단 수는 각 자리 수와 바로 옆의 수가 1만큼만 차이가 나는 수를 의미한다.

Dynamic Programming

DP로 해결할 수 있는 문제의 특징은 $n$까지의 상황이 $n+1$의 상황에 영향을 미친다는 것이다. 이러한 점화식이 성립이 되면 $n+1$의 상황을 생각할 때 그 이전의 상황, 즉 $n,n-1$번째의 상황을 심각하게 고려할 필요가 없다.

이 문제도 비슷하게 풀 수 있다. $n$자리의 계단 수의 개수를 구했다고 생각해보자. $n+1$자리의 계단수의 개수를 구하기 위해서는 $n$번째 자리만 고려하면 된다. 계단수가 되기 위한 조건이, 바로 옆 자리수와 1만큼만 차이가 나면 되기 때문이다. 만약 _이단 계단수_였다면, $n+1$자리의 계단수의 개수를 구하기 위해 $n-1,n$번째 자리를 같이 고려해야할 것이다.

주의해야할 점은, 해당 자리의 수가 0이라면 양 옆 자리의 숫자는 1이어야하고 해당 자리의 수가 9인 경우에는 8이어야 한다. 그 이외의 숫자인 경우에는 그 숫자보다 크거나 작은 수가 양 옆에 올 수 있다. 예를 들어 $n$번째 자리의 숫자가 5라면, $n+1$번째 자리의 숫자는 4 또는 6이 될 수 있다.

이러한 아이디어를 DP로 구현하기 위해 DP 테이블과 점화식을 아래와 같이 정의하였다.

• $dp[i][j]$: 끝 자리 숫자가 $j$이면서 $i$자리인 계단수의 경우의 수
• 점화식
  • $j == 0$인 경우, $dp[i][j] = dp[i-1][1]$
  • $j == 9$인 경우, $dp[i][j] = dp[i-1][9]$
  • 그 이외인 경우, $dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]$

복잡도는, $O(N \times 10)$이고, 문제에서 $N \leq 100$이므로, $O(100 \times 10)$이다.

[Source Code]

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]
        dp[i][j] %= 1000000000
print(sum(dp[n]) % 1000000000)