[DP] 10844번 계단수

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40분 + a

1. 문제 설명

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

10844번: 쉬운 계단 수

2. 접근 방식

- 길이가 i일 때를 1차 for문을 사용해서 구분하고, 2차에서는 1의 자릿수의 개수를 센다.

- 1의 자리수가 0, 9일 때는 기존 패턴과 다른 경우가 생긴다는 것을 이해해야 한다.

3. 코드

n = int(input())
dp = [[], [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

for i in range(2, 101):
    tmp = []
    for j in range(10):
        if j == 0:
            tmp.append(dp[i-1][j+1])
        elif j == 9:
            tmp.append(dp[i-1][j-1])
        else:
            tmp.append(dp[i-1][j-1] + dp[i-1][j+1])
    dp.append(tmp)
    
print(sum(dp[n]) % int(1e9))

4. 코멘트

- 초기에 규칙이 있는 줄 알고 규칙을 구현하려고 했는데, 그게 안 돼서 다른 방법을 생각했다. 

- heapq를 사용해서 구현했을 때 시간이 너무 오래걸려서 이를 dp로 구현할 수 있는 방법으로 바꿨다.

- 이 방법의 경우 끝자리가 0~9인 경우를 찾아서 더하는 형식으로 알고리즘을 설계했다. 내가 초기에 생각했던 방법과는 방향이 약간 다른 경우라고 생각한다.