[백준 2024/10/07] 10844번 쉬운 계단 수

1. 문제

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

 

2. 접근 방법

이번 문제의 경우, 처음에 dfs와 memoization으로 접근하였다.

하지만, 약점인 dp를 극복하기 위해 고른 문제인 만큼 다시 dp로 접근하려고 노력 하였다.

dfs의 길이 보이니, 역으로 dp를 생각하는 것이 까다로웠다.

 

점화식을 세워보았다.

f(i-1, n) + f(i+1, n) = f(i, n+1) 

 

1 -> 0, 2가 올 수 있고, 

2 -> 1, 3

3 -> 2, 4

4 -> 3, 5

5 -> 4, 6

6 -> 5, 7

7 -> 6, 8 

즉 앞 뒤로 값이 올 수 있으므로, 위와 같은 점화식을 세워주었다.

 

이제 n이 1일 때의 식을 세워주었다.

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 |
4 |

 

이런식으로 반복하였고, 1000000000으로 나눈 나머지를 출력하는 것도 잊지 않았다.

modulo 는 더하기 분배 법칙이 성립하므로, 편하게 나머지로 나누어 주었다.

 

3. 코드

def get_stair_num(n):
    dp = [[1] * 10 for _ in range(101)]

    dp[1][0] = 0

    for n in range(2, n+1, 1):
        for i in range(0, 10, 1):
            dp[n][i] = 0
            if 0 <= i-1 < 10:
                dp[n][i] += (dp[n-1][i-1]) % 1000000000
            if 0 <= i+1 < 10:
                dp[n][i] += (dp[n-1][i+1]) % 1000000000

    return sum(dp[n]) % 1000000000


if __name__ == "__main__":
    n = int(input())
    print(get_stair_num(n))