[bj1562] 계단 수

문제

• 백준 URL: 계단 수
• 난이도 골드 1

풀이

쉬운 계단 수의 심화 문제이다.

0~9를 모두 포함해야 한다는 것은, 다음과 같은 수를 의미한다.

9876543210

그런데, 조금만 생각해보면 알 수 있겠지만 계단 수는 수들이 모두 인접해 있고, 9->0으로의 이동이 불가능하기 때문에, 0에 대한 방문 상태와 9에 대한 방문 상태를 기록하여 두 상태가 모두 기록된 경우 0~9에 대한 숫자를 모두 포함하고 있는 상태라는 것을 알 수 있다.

따라서 추가적으로 공간을 할당하여 0에 대한 방문 상태와 9에 대한 방문 상태를 기록할 수 있도록 하고, 최종적으로 숫자 N에 대해서 0,9에 대해 모두 방문한 상태인 수들의 합을 통해 답을 구할 수 있었다.

N=int(input())
dp = [[[0]*4 for _ in range(10)]for _ in range(101)]

for i in range(1,10):
    dp[1][i][(i==9)*2] = 1
for i in range(2, N+1):
    for j in range(10):
        for bit in range(4):
            if j == 0:
                dp[i][j][bit|1] += dp[i-1][j+1][bit]
            elif j == 9:
                dp[i][j][bit|2] += dp[i-1][j-1][bit]
            else:
                dp[i][j][bit] += dp[i-1][j-1][bit] + dp[i-1][j+1][bit]

print(sum([dp[N][i][3] for i in range(10)]) % 1000000000)