[백준][파이썬] 쉬운 계단 수 10844

 

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

10844번: 쉬운 계단 수

n=1 : (1)

n=2 : (1, 2), (1, 0)

n=3 : (1, 2, 1), (1, 2, 3), (1, 0, 1)

.

.

.

 

자세히 보면 어떠한 규칙이 존재한다.

 

먼저 n이 1에서 2로 넘어갈 때를 보자.

 

n=1 에서 1 하나만 존재하는데 문제의 조건을 만족하기 위해서는 1다음에 1+1과 1-1이 존재해야한다.

 

n이 2에서 3으로 넘어갈 때도 보자.

 

(1, 2)에서 문제를 조건을 만족하기 위해서는 1, 2 다음에 2+1과 2-1이 존재해야한다.

 

(1, 0)에서는 1, 0 다음에 0+1과 0-1이 존재해야하는데 0-1은 음수이므로 불가능하다.

 

즉 이 문제는 가장 끝 숫자를 기준으로 다음 숫자를 결정할 수 있다.

 

0과 9의 경우 그 다음 경우의 수가 하나 밖에 없지만 1에서 8까지는 경우의 수가 두 개 있다.

 

이제 배열을 만들건데 배열의 인덱스는 곧 가장 끝 숫자이다.

 

n=3 : (1, 2, 1), (1, 2, 3), (1, 0, 1)

 

이 경우 끝 숫자가 1이 2개 3이 하나이므로 배열로 나타내면 아래와 같다.

 

0	1	2	3	4	5	6	7	8	9
0	2	0	1	0	0	0	0	0	0

 

이제 알고리즘을 일반화할 차례이다.

 

길이가 n이고 끝 숫자가 m인 계단 수는 길이가 (n-1)이고 끝 숫자가 (m-1)인 계단 수와 길이가 (n-1)이고 끝 숫자가 (m+1)인 계단 수의 합이다.(1<= m <=8)

 

이를 코드로 나타내면 아래와 같다.

n=int(input())
dp = [1]*10
dp2 = [1]*10
dp[0]=0
for _ in range(n-1):
    for i in range(10):
        if i==0:
            dp2[i]=dp[i+1]
        elif i==9:
            dp2[i]=dp[i-1]
        else:
            dp2[i]=dp[i-1]+dp[i+1]
    dp = dp2.copy()
print(sum(dp)%1000000000)