다이나믹 프로그래밍4

#10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 디피 문제를 풀다가 또 한번 막히셨단다... (지긋)

 

내가 생각한 점화식은 

약간 이런 느낌이었다.

 뭔가 야간 이런 느낌으로, 0, 9일 때는 하나씩 파생되고, 1~8일 때는 2개씩 파생되는 모양새가 다른 패턴이 있을 것 만 같은 느낌을 주긴 했다. 그래도 위에서 먼저 찾았던 점화식을 적용해 봤지만

 

당연히 틀림.

실버 1레벨의 문제니까 다르다 이건가

 

고민을 하던 끝에 검색을 했다.

n = int(input())

mod = 1000000000
dp = [[0 for x in range(10)] for y 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]) % mod)

dp 리스트를 보면 자리수를 거듭할 수록 1차원 index를 갖는다.

dp[0] -> 0의 자리 수 일 때의 계단수

dp[1] -> 1의 자리 수 일 때의 계단수

 

2차원 index는 각 인덱스를 숫자로 해석하면 된다

dp[1][0] -> 1의자리 수 일때 0이 갖는 계단수의 경우 -> 0가지

dp[1][1] -> 1의자리 수 일때 1이 갖는 계단수의 경우 -> 1가지

 

조금 난해할 수 있지만 저런 의미이다.

이걸 다이나믹 프로그래밍 방식으로 풀어나간다면 이렇게 된다.

 

약간 느낌이 올까..?

계단수라는건 '어떤 수'와 1차이 나는 수가 옆에 오는 경우를 말하는데

한 자리수가 늘어나는 상황에서 올 수 있는 경우의 수는

그 자리수 보다 작은 자리수에서 구해놓은 경우의 수 중,

'어떤 수' 보다 1차이 나는 자릿수가 갖고있는 경우의수를 모두 더해주면 된다.

그림상에서는 대각선 위에 있는 값을 가져와 더해주면 된다.

약간 감이 왔으면 좋겠다.

나도 처음 이해할 때는 이게 뭔가 싶었지만 알고보니 참 쉬워서 당황했다.

 

index 0의 경우에는 왼쪽 위가 없다.

index 9의 경우에는 오른쪽 위가 없다.

 

따라서 점화식은

0일 때, 9일 때, 1~8일 때로 나눠서 진행해주면 된다.

 

이후 각 숫자의 경우의 수를 모두 더해주면 해당 자리수의 경우의 수가 나온다.