[백준] 1562. 계단 수 - Python

[Gold I]

 

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

1562번: 계단 수

 

풀이

비트마스킹을 이용한 DP 문제.

기본적인 아이디어는 2차원 DP를 생각하면 쉽게 떠올릴 수 있는데,

dp[N][i] 일 때, dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 과 같은 점화식(i==0, i==9 예외) 으로 풀이할 수 있다.

 

다만 위의 경우는 0부터 9까지 숫자가 모두 등장하는 계단 수 라는 조건을 무시했을 때의 풀이법.

이 문제는 위 조건을 만족하는 수의 개수만을 구해야 하므로, 기존 풀이를 응용하여 풀이할 수 있다.

 

기존 2차원 배열이 아닌, 3차원 배열로 선언하여 마지막 차원을 bitmasking으로, 0~9까지의 방문 여부를 확인하며 3중 반복문으로 Bottom-Up 식으로 저장하며 나아가면 된다.

 

AC.

N = int(input())
MOD = 1e9
# dp[N번째 수][마지막 수][방문한 수 bitmasking(0~1023)]
dp = [[[0]*1024 for _ in range(10)] for _ in range(N+1)]

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

# n = N번째 수
for n in range(2, N+1):
    # i = 마지막 방문 숫자가 i
    for i in range(10):
        # 0~9까지 모든 수를 방문해야 한다는 조건이 있으므로, 방문 여부를 bitmasking을 통해 저장해야 함.
        for bit in range(1024):
            if i == 0:
                dp[n][i][bit | (1<<i)] += dp[n-1][i+1][bit]
            elif i == 9:
                dp[n][i][bit | (1<<i)] += dp[n-1][i-1][bit]
            else:
                dp[n][i][bit | (1<<i)] += dp[n-1][i-1][bit] + dp[n-1][i+1][bit]
            
            dp[n][i][bit | (1<<i)] %= MOD
    
res = 0
for i in range(10):
    res += dp[N][i][2**10-1]

print(int(res%MOD))