[Python] 백준 1562 계단 수

 

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다.

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

 

 

 

 

 

 

 

난이도

골드 1

 

 

 

 

 

 

코드

import sys

n = int(sys.stdin.readline())
dp = [[[0 for _ in range(2**10)] for _ in range(10)] for _ in range(n+1)]
answer = 0
mod = 1000000000

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

for i in range(1,n) : # n-1 번째 까지해서 다음 거 저장
    for j in range(10) : # 마지막숫자
        for k in range(2**10) : # 방문현황
            tmp = dp[i][j][k] # 갯수
            if j < 9 :
                nextJ = j + 1
                nextV = k | (1 << nextJ) # 방문처리
                dp[i+1][nextJ][nextV] += tmp
                dp[i+1][nextJ][nextV] %= mod
            if j > 0 :
                beforeJ = j - 1
                nextV = k | (1 << beforeJ)
                dp[i+1][beforeJ][nextV] += tmp
                dp[i+1][beforeJ][nextV] %= mod
S = (1<<10)-1

for j in range(10) :
    answer += dp[n][j][S]
    answer %= mod

print(answer)

 

 

 

 

풀이

비트필드를 이용한 DP문제다.

dp배열 dp[i][j][k]를 만들어 풀었다.

i : 현재 자리수 

j : 마지막 자리에 위치한 숫자

k : 현재까지 사용된 숫자들을 비트마스크로 표현한 값. 예를 들어 모든 값이 사용되었으면 0b11111111111 으로 표현된다.

 

초기상태는 j가 1부터 9까지 돌면서 해당 비트값을 1로 표현해 갯수를 1로 초기화했다.

0부터 시작하는건 세지 않기 때문에 제외

 

j가 0일때와 9일 때만 신경쓰면서 다음 자리수(j-1,j+1)의 마지막 자리 수를 방문처리하여 현재 값을 더해준다.

 

정답은 마지막 자리에 위치한 숫자가 0부터 9까지일 때 모든 숫자가 한번씩 사용된 경우의 수 (k가 0b11111111111 일 때) 를 모두 더해 답을 도출했다.

 

 

 

비트마스킹을 제대로 이용해 본 적은 거의 처음인것같다. 

잘 익혀두면 유용하게 쓰일듯하다.

 

 

 

원래 값(value)에 num번 째 원소 추가

value |= (1 << num)

 

 

num번째 원소 삭제

value &= ~(1 << num)