[BOJ] 1562 - 계단 수 (Python)

 

 

아이디어 #1

 

비트마스킹으로 0~9의 수를 모두 사용했는지 여부를 확인하여 DP 테이블을 채워 값을 구한다.

 

 

풀이 #1

 

N, 시작 숫자, 사용 표시 비트 정보를 저장하는 3차원 리스트 dp를 생성하고, 0~9의 숫자에 대해 초기값을 설정한다.

for문에서 0부터 1023(2진수 1111111111)까지의 비트로 해당 숫자를 사용하는 경우의 수를 dp에 누적하여 더해 나간다.

0과 9는 각각 1과 8에서 오는 경우를 더하고, 나머지 숫자들은 1만큼 차이나는 숫자로부터 오는 경우를 더한다.

시작 숫자가 1~9인 계단 수의 개수를 1,000,000,000로 나눈 나머지를 구해 출력한다.

 

N = int(input())
dp = [[[0]*(1<<10) for _ in range(10)] for _ in range(100)]
for i in range(10):
    dp[0][i][1<<i] = 1
for i in range(N-1):
    for visited in range(1<<10):
        dp[i+1][0][visited|1] += dp[i][1][visited]
        dp[i+1][9][visited|(1<<9)] += dp[i][8][visited]
        for j in range(1, 9):
            dp[i+1][j][visited|(1<<j)] += dp[i][j-1][visited]+dp[i][j+1][visited]
res = 0
for i in range(1, 10):
    res = (res+dp[N-1][i][-1])%1000000000
print(res)

 

 

0과 9가 오는 경우를 구하는 부분을 for문 밖으로 뺀 코드가 더 빨랐다.

# 1.
for visited in range(1<<10):
    for j in range(10):
        if j == 0:
            dp[i+1][0][visited|1] += dp[i][1][visited]
        elif j == 9:
            dp[i+1][9][visited|(1<<9)] += dp[i][8][visited]
        else:
            dp[i+1][j][visited|(1<<j)] += dp[i][j-1][visited]+dp[i][j+1][visited]

# 2. 더 빠른 코드
for visited in range(1<<10):
    dp[i+1][0][visited|1] += dp[i][1][visited]
    dp[i+1][9][visited|(1<<9)] += dp[i][8][visited]
    for j in range(1, 9):
        dp[i+1][j][visited|(1<<j)] += dp[i][j-1][visited]+dp[i][j+1][visited]

 

 

 

아이디어 #2

 

다른 분의 아이디어를 참고해보니 0과 9를 둘 다 사용한 상태라면 0~9를 모두 사용한 상태와 같았다.

0을 사용한 경우 1을 더하고, 9를 사용한 경우 2를 더하면 합이 3으로 크기 1024를 4로 줄일 수 있다.

 

 

풀이 #2

 

dp 저장 시 0과 9는 각각 1과 2에, 1~8의 숫자들은 0에 사용 표시를 하는 것 외에 나머지 동작 방식은 풀이 #1과 같다.

 

N = int(input())
dp = [[[0]*4 for _ in range(10)] for _ in range(100)]
dp[0][0][1] = dp[0][9][2] = 1
for i in range(1, 9):
    dp[0][i][0] = 1
for i in range(N-1):
    for visited in range(4):
        dp[i+1][0][visited|1] += dp[i][1][visited]
        dp[i+1][9][visited|2] += dp[i][8][visited]
        for j in range(1, 9):
            dp[i+1][j][visited] += dp[i][j-1][visited]+dp[i][j+1][visited]
res = 0
for i in range(1, 10):
    res = (res+dp[N-1][i][-1])%1000000000
print(res)