[다이나믹 프로그래밍/파이썬] 백준 1562번 : 계단 수 / 골드 1

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

1562번: 계단 수

n = int(input())
dp = [[[0 for _ in range(1<<10)] for _ in range(10)] for _ in range(n+1)]

# init
for i in range(10):
    dp[1][i][1 << i] = 1

# dp
for i in range(2, n+1):
    for j in range(10):
        for k in range(1 << 10):
            if j == 0:
                dp[i][j][(1 << j) | k] += dp[i - 1][j + 1][k]
            elif j == 9:
                dp[i][j][(1 << j) | k] += dp[i - 1][j - 1][k]
            else:
                dp[i][j][(1 << j) | k] += dp[i - 1][j - 1][k]
                dp[i][j][(1 << j) | k] += dp[i - 1][j + 1][k]

            dp[i][j][(1 << j) | k] %= 1000000000

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

상당히 어려운 dp+비트마스킹 문제다.

dp의 구조는 다음과 같다.  =>  dp[글자수][시작 숫자][방문 숫자(이진법)]

이때 방문 숫자는 비트마스킹을 적용해준다. 따라서 3차원 dp를 구성하였다.

 

글자수가 2이고 앞자리가 1로 시작할 때 dp[2][1]로 표현이 될 수 있다.

이때는 두번째 글자에 0이나 2가 올 수 있기 때문에 다음이 성립하게 된다.

 

1 다음에 0이 오는 경우의 수

dp[2][1][ 0000000010 (2) | 0000000001 (2)]  +=  dp[1][0][ 0000000001 (2)]

 

1 다음에 2가 오는 경우의 수

dp[2][1][ 0000000010 (2) | 0000000100 (2)]  +=  dp[1][2][ 0000000100 (2)]

 

 

이런 방식으로 dp 테이블을 완성시켜주고, 답을 구해내면 된다.

제일 앞자리엔 0이 올 수 없으니

   dp[n][1][1111111111(2)]

+ dp[n][2][1111111111(2)]

            .........

+ dp[n][9][1111111111(2)] 

가 답이 된다.