백준 1562

문제

45656이란 수를 보자.

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

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

비트마스킹을 이용한 다이나믹 프로그래밍입니다. 0부터 9까지의 수를 모두 사용해야 하므로 총 몇개의 수를 이용했는지 기록해야 합니다. 예를 들어 [9,8,7] 이후에 [9,8,7,?]으로 갈때 Bit: 0 0 0 0 0 0 0 1 1 1을 지녀야 합니다. 최종적으로 Bit: 1 1 1 1 1 1 1 1 1 1인 경우의 수를 계산하면 됩니다.

전체적인 풀이는 다음과 같습니다.

• 3차원 배열 dp[i][j][k]를 먼저 만듭니다. i: 비트정보, j: 자릿 수, k: 끝나는 수 입니다.

• 처음 시작할때 값을 1로 초기화 합니다. 2에서 출발하는 경우 비트는 1«2 이고 자릿수는 0, 끝나는 수는 2입니다. ex) dp[1«2][0][2] = 1

• 자릿수 i만큼 반복합니다.

• 끝나는 수인 0~9를 순회합니다.

• 모든 비트에 대하여 순회합니다. 이때, 이전 단계의 계단의 높이가 한칸 높거나 낮은 경우의 수를 더해줍니다.

  ex) 1번째 자리가 1, 2번째 자리가 2, 3번째 자리가 3인 경우 dp[111000000][3][3]은 dp[110000000][2][4]과 dp[110000000] [2][2]를 더해준 값입니다.

  • 비트값을 | 처리 해줘서 해당위치의 0을 1로 변환합니다.

• 최종적으로 dp[1023][n-1]의 합을 return 합니다.

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)인 경우를 더하는 수가 될 것이다.
        for bm in range(1024):
            # 0과 9는 앞뒤로 한칸씩 밖에 못더해줌
            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

print(sum(dp[1023][n-1]) % 1000000000)