[python: DP] BOJ10844 - 쉬운 계단 수

정말 DP에 소질이 없는 나는 DP 문제를 많이 풀어야 할 것 같다... 왜 어떻게 접근해야겠다는 생각조차 못할까?

일단 하나 하나 적어보자

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

---

입력 예제

2

출력 예제

17

---

문제 풀이법

첫번째, 자리수가 1일 때를 보자

자리수/	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2
3

두번째, 자리수 2일 때를 쌓아보자

자리수/	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3

세번째, 자리수 3일 때를 쌓아보자

자리수/	0	1	2	3	4	5	6	7	8	9
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

표 안에 적힌 숫자들에 각 대각선을 합치면 그 숫자가 되는 것을 볼 수 있다. 이것을 점화식으로 구현하면,

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

다음과 같다. 그렇지만 0과 9는 각 대각선이 없으므로 조건문이나 아예 지정하여 처리해준다.

그것을 소스코드로 구현하면 ?!

---

소스코드

import sys

n = int(sys.stdin.readline())

dp = [[0] * 10 for _ in range(n+1)]
dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

# dp의 의미? dp[3][7]: 6으로 끝나는 3자리 수의 계단 수의 개수

for i in range(2, n+1):
  dp[i][0] = dp[i-1][1] # 0으로 끝나는 경우
  dp[i][9] = dp[i-1][8] # 8로 끝나는 경우

  for j in range(1, 9):
    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] # 1-8로 끝나는 경우

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

---

다음과 같다. DP 문제는 일단 손으로 다 3까지 계산을 해보고 그 안에서 규칙을 찾아야 하는 것이 핵심이라는 것을 알았다. 하지만 자리 수, 숫자들을 생각하는 것이 무척 어렵다. 여러 문제 풀게 되면 dp를 무엇으로 놓아야 할지 감이 오게 될까? 그 감이 얼른 왔으면 좋겠다.