[백준][Python] 1562 계단수

비트마스크 문제. 0~9까지의 숫자를 총 자릿수를 늘려가고 뒷자릿수에 따른 경우의수를 더해주며 dp진행합니다.

 

초깃값은 100000000, 010000000,00100000 ....000000001 시작값에 대해 불을 켜주고 경우의수 1을 더해주고 시작합니다.

dp[x][y][z]에서 x는 비트숫자(불켜진 모든 경우의수), y는 자릿수(0:1자리), z는 마지막자리의 숫자.

 

import sys
input = sys.stdin.readline

n = int(input())

# dp: 비트 정보, 자릿 수, 끝나는 수
dp = [[[0] * 10 for _ in range(101)] for _ in range(1 << 10)]

# 처음 시작값을 1로 초기화
for i in range(1, 10):
    dp[1<<i][0][i] = 1

# 자릿수 만큼 순회
for i in range(1, n):
    # 0 ~ 9까지 순회
    for e in range(10):
        # 모든 비트의 대하여 순회
        # 예를 들어, i=3라고 하자. (3번쨰 순회)
        # 3으로 끝났는데 비트가 000000110인경우가 있다고 하자. e가 3이면서 비트가 000001110을 구하고자 한다.
        # 그렇다면, (4,000000110) 과 (2,000000110)인 경우를 더하는 수가 될 것이다. 3으로 끝나고 000000110 -> 000001110즉 3에서 4를 추가하고싶다면
        # 1024는 계단의 숫자를 썻는지 안썼는지에 대한 경우의 수. 거기에 저장하는건. 그 전 자릿수가 +1이나 -1로 끝난것의 합을 모두 더해주는것.
        for bm in range(1024):
            # 0과 9는 앞뒤로 한칸씩 밖에 못더해줌 즉 0은 e<9의 전자릿수 1에서의 합만 받고 9는 e>0의 전자릿수 8의 합만 받음.
            if e < 9:
                dp[bm | (1<<e)][i][e] = (dp[bm | (1<<e)][i][e] + dp[bm][i-1][e+1]) % 1000000000
            if e > 0:
                dp[bm | (1<<e)][i][e] = (dp[bm | (1<<e)][i][e] + dp[bm][i-1][e-1]) % 1000000000

# 그래서 1111111다 켜지고 자릿수가 n인 dp의 값을 모두 더해주면 됨(0~9로 끝나는 모든 경우의수의 값의 합.)
print(sum(dp[1023][n-1]) % 1000000000)