[Python] 백준 10844번: 쉬운 계단 수 풀이

 

소스코드

n = int(input())
# dp 초기화 (최소 1개는 있으므로) 
dp = [[1]*10 for _ in range(n+1)]
# dp[i][j] 에서 i은 자리수, j는 수의 마지막 숫자
# 1자리 수는 0이 끝에 올 수 없으므로 0개로 저장
dp[1][0] = 0
if n!= 1 :
    for i in range(2, n+1):
        for j in range(0, 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)

 

 

dp채우기/ dp[i][j] / i는 자리수, j는 수의 끝에 오는 숫자

 마지막

자리 숫자 | 0  1  2  3  4  5  6  7  8  9

__________________________________________          

자리수(N)  

1            0  1  1  1  1  1  1  1  1  1    

2            1  1  2  2  2  2  2  2  2  1

3            1  3  3  4  4  4  4  4  3  2

 

 자리수마다 마지막 자리 숫자에 따른 경우의 숫자를 나열해보았다.1자리 일 때는 0은 올 수 없고, 나머지 숫자는 1개의 경우이다.2자리 일 때, 끝에 0이 오는 경우는 10, 1이 오는 경우는 21, 9가 오는 경우는 89 이고, 나머지 숫자들이 올 때에는+- 1의 숫자 즉 2개의 방법이 있다.

3자리 일 때, 끝에 0이 오는 경우는 0앞에 1이 오는 경우밖에 없으므로 2자리 일때 끝에 1이 오는 경우, dp[2][1] 과 동일 할 것이다.

3자리 일 때, 끝에 1,2...,8 이 올 때는 이러하다.

예 ) __1일 경우, _21 이거나 _01 일 것이므로 dp[3][1] = dp[2][2] + dp[2][0] 와 동일하다.

3자리 일 때, 끝에 9가 오는 경우는 9앞에 8이 오는 경우밖에 없으므로 2자리 일 때 끝에 8이 오는 경우, dp[2][8] 과 동일 할 것이다.

 

따라서 끝자리 수에 0과 9가 오는 경우에만 각각 그 이전자리숫자의 끝에 1과 8이 오는 경우와 동일하고,

나머지 숫자가 끝에 올 때에는 이전자리수의 끝에 그 숫자의 앞 뒤 가 오는 경우의 합과 같다.

 

즉, 관계식을 세워보면

 

j=0,  dp[i][j] = dp[i-1][1] j=9,   dp[i][j] = dp[i-1][8] j=1~8,   dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

임을 알 수 있다.