[백준]10844번 쉬운 계단 수 - DP

 

n = int(input())

dp = [[0] * 10 for i in range(n)]  # 0~9의 인덱스를 가지고, n의 자릿수를 가진 이중 리스트 초기화.
dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]  # 한자리 숫자일 때 미리 초기화.

for i in range(1, n):
    for j in range(10):
        if j == 0:  # 0이면 전 자릿수의 j+1 만 더함
            dp[i][j] = dp[i - 1][j + 1]
        elif j == 9:  # 9 이면 전 자릿수의 j-1 만 더함
            dp[i][j] = dp[i - 1][j - 1]
        else:  # 1~8 은 전 자릿수의 j-1, j+1 이 올 수 있으므로 두개를 더함
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

print(sum(dp[n - 1]) % 1000000000)  # 출력

 

 코드 설명

이중 dp 리스트를 활용하여 문제를 풀이한다. 먼저 0~9의 인덱스를 가지는 리스트를 위해 *10 만큼 설정한다. 또한 자릿수를 위해 n만큼의 이중리스트를 생성한다.

한자리 숫자일 경우에는 1~9의 인덱스 모두가 자신이 계단수 이므로 1로 초기화 하여 준다. (0 인덱스는 사용하지 않는다)

두자리 숫자의 경우부터 반복을 진행하면서 조건에 맞게 점화식으로 계산한 후 출력한다.

 

Point : 2자리수 이상부터는 점화식을 통해 판별해야 한다.

만약 끝나는 수가 0이라면 이전 수에는 1만 올 수 있다. 9의 경우에는 이전 수로 8만 올 수 있다. 그 외의 경우에는 +- 1의 숫자가 올수 있다.

3가지의 case를 만들 수 있다.

case 1 : 마지막 자리가 0으로 끝나는 경우 -> 전 자릿수에 1만 올 수 있다. 따라서 dp[i-1][j+1] 의 값을 이용한다.

case 2 : 마지막 자리가 9로 끝나는 경우 -> 전 자릿수에 8만 올 수 있다. 따라서 dp[i-1][j-1]의 값을 이용한다.

case 3 : 그 외의 경우 -> dp[i-1][j-1] + dp[i-1][j+1] 의 값을 이용한다.