[BOJ] Q1562 계단수

[BOJ] Q1562 계단수

Question

Language: Python

Difficulty: Gold 1

해당 문제는 bitmasking 과 DP를 활용하는 문제이다.

계단수 중에서도 0~9 사이에 수가 모두 존재하는 계단수를 찾아야하므로, 이를 판별하기 위해 비트마스킹을 사용하도록 한다.

또한, 마지막 수를 알고 있어야, 어떤 숫자라를 추가 할 수 있는지 여부를 판단할 수 있기 때문이다.

그래서, dp를 [길이][마지막수][비트값]을 활용해서 표현하도록 한다.

비트값이 1023이 되도록 하면, 0~9 까지의 수를 모두 포함하고 있을 의미하게 된다.

위와 같은 dp에 대한 점화식은 아래와 같이 표현할 수 있게 된다. 아래와 같이 last(마지막 수)를 기준으로 +1, -1 위치에서 올수 있다, 즉, 마지막에 사용한 숫자가 3이 되러면 ,직전에 2 또는 4을 사용하게 된 경우 말고는 존재하지 않는다.

dp[length+1][last][used | 1 << last] += dp[length][last+1][used]
dp[length+1][last][used | 1 << last] += dp[length][last-1][used]

Solution

def solution():
    dp = [[[0 for _ in range(1024)] for _ in range(10)] for _ in range(num+1)]
 
    for i in range(1, 10):
        dp[1][i][1<<i] = 1
 
    for length in range(num):
        for last in range(10):
            for used in range(1024):
                if last < 9:
                    dp[length+1][last][used | (1<<last)] = (dp[length+1][last][used | (1<<last)] + dp[length][last+1][used]) % 1000000000
                if last > 0:
                    dp[length+1][last][used | (1<<last)] = (dp[length+1][last][used | (1<<last)] + dp[length][last-1][used]) % 1000000000
    
    return sum([dp[num][i][1023] for i in range(10)]) % 1000000000

if __name__ == "__main__":
    num=int(input())
    print(solution())