백준: 11057 오르막 수

문제

11057번: 오르막 수

 

문제 풀이

 이전에 푼 10844 쉬운 계단 수에 대한 풀이와 유사한 방식으로 풀 수 있는 문제이다. 차이점은 0으로 부터 시작할 수 있고 수가 중복되어도 된다는 것이다. 따라서 n에 따른 경우의 수들은 f(n) = f(n - 1) + f(n) 점화식을 통해 구할 수 있다. 이는 3으로 끝나기 위해서는 앞의 숫자들이 0, 1, 2가 되어도 되기 때문에 이는 앞에 구한 경우의 수를 합산해주어야 하기 때문이다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline()) - 1
    nums = [1] * 10

    for _ in range(n):
        for i in range(1, 10):
            nums[i] = nums[i] + nums[i - 1]

    print(sum(nums) % 10007)