9461 파도반수열

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

N = int(input())

dp_table = [[0 for _ in range(10)] for _ in range(N)]
dp_table[0] = [1,1,1,1,1,1,1,1,1,1]

if N == 1 :
    print((sum(dp_table[N-1])-1)%1000000000)

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

3. 문제 풀이

이 문제도 전형적인 규칙을 찾는 문제다. N이 1일때부터 하나씩 트리형식으로 그림을 그려나가면 규칙을 쉽게 찾아갈 수 있다. N 번째의 i(i=1,2,…8)로 시작하는 계단의 수는 N-1 번째의 i-1,i+1번째의 계단의 수를 이어 붙이면 간단하게 해결할 수 있다. 그러나 여기서 핵심은 0과 9이다. 0은 자신의 왼쪽 수가, 9는 자신의 오른쪽 수가 없다. 따라서 0은 [N-1][i+1]만을 더하고, 9는 [N-1][i-1]을 더해야한다. 여기서 더 핵심은 0을 꼭 같이 구해줘야하는 것이다. 0으로 시작하는 계단의 수는 계단의 수가 아니라고 했지만, 0의 가지를 생각해야하는 이유는 1의 가지에 0이 쓰이기 때문이다. 따라서 dp table을 1~9까지만 만들 것이 아니라, 0부터 9까지 만들어야함을 잊지말자.