[백준] 1562 - 계단 수

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

1562번: 계단 수

간단한 dynamic programming 문제이다.

 

dp에 이용되는 숫자의 특징은 2가지다.

• 수의 마지막에 위치하는 숫자
• 현재까지 사용된 숫자

현재까지 사용된 숫자의 경우, bitmask를 사용하여 10진수로 변환한다.

ex) 2, 4, 5 를 가짐 -> 0000110100(2) -> 52

 

위 두가지 특징을 가진 계단 수의 개수를 2차원 배열에 저장한다.

 

n-1 길이의 계단 수들로부터 n 길이의 계단 수의 계단 수의 개수를 구한다.

배열을 전부 순회하며 해당 수의 가장 뒷자리에 올 수 있는 수를 추가한 뒤, 이를 n 길이의 2차원 배열에 추가한다.

 

<Python 코드>

n = int(input())
 
re = 0
dp = [[0 for _ in range(1024)] for _ in range(10)]
 
for i in range(1, 10):
    dp[i][1<<i] = 1
 
for i in range(1, n):
    dp_next = [[0 for _ in range(1024)] for _ in range(10)]
    for e in range(10):
        for bm in range(1024):
            if e < 9:
                dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e+1][bm]) % 1000000000
            if e > 0:
                dp_next[e][bm | (1<<e)] = (dp_next[e][bm | (1<<e)] + dp[e-1][bm]) % 1000000000
    dp = dp_next
 
print(sum([dp[i][1023] for i in range(10)]) % 1000000000)