https://www.acmicpc.net/problem/10844

🥚문제

---

🥚입력/출력

---

🍳코드

import sys

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

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

for num in range(2, n+1):
    new_list = []
    for i in range(10):
        answer = 0
        if i - 1 >= 0:
            answer += dp[num-1][i-1]
        if i + 1 <= 9:
            answer += dp[num-1][i+1]
        new_list.append(answer)
    dp[num] = new_list

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

---

🧂아이디어

• 처음으로 풀어 본 2차원 list로 푸는 dp! memoization만 되면 리스트의 형태가 무슨 상관인가!

• 1차원 list로만 보고 dp[i] = dp[i-1]*2 - (도대체 몇?) 으로만 생각하느라 시간을 많이 날렸다.

• 그래도 중요한 아이디어는 생각해 낼 수 있었다. 1의자리 숫자에만 focus를 하면 된다는 것! 그 1의자리 숫자를 +1, -1 하여 계단수를 만드는데, +1, -1한 값이 -1 또는 10이면 계단수에서 탈락한다.

• https://pacific-ocean.tistory.com/151 포스팅에서 도움을 많이 얻었다.