[Python] 10844 - 쉬운 계단 수 (실버1)

1. 문제 설명

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

10844번: 쉬운 계단 수

2022 연세대 알고리즘 대회에 나온 문제에서 막혔어서 끝나고 이 문제를 풀어봤었다.

물론 이걸 푼다고 그 문제가 풀리진 않았다...

 

---

2. 아이디어

테스트 케이스에서 힌트를 하나 얻어가야 하는데 input이 1일 때, output이 9가 나온다.

문제 조건에선 0으로 시작하는 수는 계단 수가 아니라고 했으므로 이후에는 0이 나올 수 도 있다.

계단수는 1~9에서 시작해서 0~9범위에서 움직이는 수열이다.

 

이 문제는 dp[N번째 계단][현재 위치] = 경우의 수로 풀면 쉽게 풀린다.

1번 (index == 0)인 경우에는 모든 경우의 수를 1로 채우고 다음으로 이동할 때, 구간별로 생각해주어야 한다.

 

0번의 경우, 1번 계단에서 오는 경우가 아니면 올 수 없음.

9번의 경우, 8번 계단에서 오는 경우가 아니면 올 수 없음

1~8번의 경우, x-1번 계단 혹은 x+1번 계단에서 오늘 경우를 더하면 됨.

 

답은 위의 조건대로 조건을 나누어서 경우의 수를 더하고 마지막에 출력하면 끝난다.

 

---

3. 코드

def solution():
    n = int(input())
    cache = [[0]*10 for _ in range(n)]
    for idx in range(1, 10):
        cache[0][idx] = 1

    for i in range(1, n):
        for j in range(10):
            if j == 0:
                cache[i][j] = cache[i-1][1]
            elif j == 9:
                cache[i][j] = cache[i-1][8]
            else:
                cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
    print(sum(cache[n - 1]) % 1000000000)

solution()