쉽다매... '쉬운' 계단 수라며...

10844: 쉬운 계단수

1. 다른 풀이

import sys

N = int(sys.stdin.readline())
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]

print(sum(dp[N]) % 1000000000)

모든 걸 깨우친 지금에서야 아~ 괜찮네~ 싶지만 풀이를 이해하기까지 조금 어려웠다. 인터넷에 여러 글을 참고하면서 깨우친 듯하다.

처음에는

dp = 점화식

이라고 생각을 하니까 1차원적으로 전체 가짓수의 규칙을 찾으려고 했다. 하지만 이렇게 되면 정말... 일단 가짓수 세는 것부터 무지막지하게 많아지고 틀릴 가능성이 다분하다.

dp를 2차원적으로 이용할 수 있다는 사실도 신기했다. 그래서 풀이에 대해서 설명하자면,

일단 여기서 dp는 만약 n=2라고 하면,
dp[2][1의 자리수에 올 수 있는 수] 라고 할 수 있다. 아래 사진을 보자.

for i in range(1, 10):
    dp[1][i] = 1

n=1일 때 가짓수는 9가지라는 사실이 자명하다.

이를 바탕으로 n=2일 때의 가짓수를 구한다고 생각해보자. dp가 dp[2][1의 자리수에 올 수 있는 수] 이처럼 정의된다고 하였으니, 결론적으로 [1의 자리수에 올 수 있는 수]에 들어올 값은 위 그림에서 받는 화살표의 개수라고 생각하면 편하다.

두 자리 수에서 0과 9는 10, 89 밖에 되지 못한다.

따라서 받는 화살표는 1개씩이다. 1 역시 21 밖에 되지 못하므로 받는 화살표는 1개이다.

즉, 1의 자리가 0일 때는 n=1일 때 dp[1][1]의 값을 가져온다. 1의 자리가 9일 때는 dp[1][8]의 값을 가져온다. 하지만 나머지 1~8일 때는 index의 $\pm1$의 값의 합을 가져온다.

이를 코드로 일반화 해보자.

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 문제를 풀 때는 점화식이 제일 중요하고, 다음으로 그 규칙을 어떤 식으로 찾는가가 정-말 중요하다는 것이다...!

오늘도 신기한 알고리즘의 세계 끄읕 ~!