쉬운 계단 수 (BOJ-10844)
in ALGORITHM
‘시간제한 1초, 메모리제한 256MB, BOJ-10844’
쉬운 계단 수 (BOJ-10844)
다이나믹 프로그래밍인 느낌은 있었는데 어떤식으로 점화식을 세워야할지 전혀 몰랐었다. 결과값들의 규칙성을 찾지 못해서였다. 결과값이 아니라 과정에서 규칙을 찾을 수 있었다.
제일 뒷자리에 오는 숫자의 경우의 수를 구하면 규칙을 알 수 있다.
계단 수는 이어지는 수이므로 n이 1일때는 뒷자리가 0일때를 제외하고 1부터 9까지 모두 1번씩 온다.
n이 2일 때는 뒷자리가 0인 경우는 1번, 뒷자리가 9인 경우도 1번이다.
ex) 10, 89
이는 0과 9가 이어지는 수가 1개뿐이기 때문이다.
0과 9를 제외하곤 계단수는 자기보다 1 작은수와 1 큰수 2가지 경우이므로, 이전 n에서 현재 수보다 1이 작은수의 경우의 수와 현재 수보다 1이 큰수의 경우의 수를 합치면 자신의 계단수의 경우의 수가 나온다.
이 부분이 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]이다.
위의 표에서 보면 뒷자리가 0인 경우는 이전 n의 뒷자리가 1인 경우의 수이고, 뒷자리가 9인 경우는 이전 n의 뒷자리가 8인 경우의 수이다.
다이나믹 프로그래밍은 항상 점화식 도출이 어려운거 같다;;
n = int(input())
dp = [[0 for i in range(10)] for _ in range(101)]
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)
