[BOJ] 1562번 : 계단 수 [G1]

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

1562번: 계단 수

 

 

BOJ 1562번

 

 

문제

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

예제 입력 1 복사

10

 

예제 출력 1 복사

1

 

 

---

내 풀이

어제 '쉬운 계단 수'를 푼 상태에서 문제를 접하여서 '쉬운 계단 수'를 풀때와 같이 dp로 생각을 시작하였다.

하지만 0~9 모든 수가 존재하는 계단 수를 구해야 하기 때문에 단순히 dp만 사용해서는 풀 수가 없었다.

따라서 힌트를 본 후, 생각해낸게 '비트마스킹'

사실 엄밀히 말하자면 비트마스킹을 사용한 알고리즘 풀이는 아니지만 비트마스킹에서 아이디어를 착안하였다.

 

밑에 코드에서 확인할 수 있지만 3차원 리스트에 대해 부연설명을 하자면

dp[i][j][k] = [ i 번째 자릿수 중, 숫자 j로 끝나는 수에 대해,  [0, 9 중 아무것도 포함하지 않을 때, 0만 포함할 때, 9만 포함할 때, (0,9) 모두 포함할 때] ]

 

로 3차원 리스트를 선언하였다.

 

계단 수 이기 때문에 0과 9를 포함하는 수는 곧 0~9를 포함하는 수라고 할 수 있다.

따라서 0을 포함하는 수와 9를 포함하는 수를 체킹하여 '0과 9 모두 체킹되어 있는 수'만 계단수로 판별하는 방식으로 문제를 해결하였다.

 

import sys
input = sys.stdin.readline

N = int(input())

if N < 10:
    print('0')
elif N == 10:
    print('1')
else:
    dp = [[[0 for _ in range(4)] for _ in range(10)] for _ in range(N+1)]
    # dp[i][j][k] : a number of i ciphers, finished by 'j', [nothing, reach 0, reach 9, reach 0 and 9]
    for i in range(1, 9):
        dp[1][i][0] = 1

    dp[1][9][2] = 1

    for i in range(2, N+1):
        # 0 only come from 1
        dp[i][0][1] = dp[i-1][1][0] + dp[i-1][1][1]# ~(i-1) only touch 0
        dp[i][0][3] = dp[i-1][1][2] + dp[i-1][1][3] # ~(i-1) touch 9 => 0, 9 touch

        for j in range(1, 9):
            for k in range(4):
                dp[i][j][k] = dp[i-1][j-1][k] + dp[i-1][j+1][k]

        # 9 only come from 8
        dp[i][9][2] = dp[i-1][8][0] + dp[i-1][8][2]# ~(i-1) only touch 9
        dp[i][9][3] = dp[i-1][8][1] + dp[i-1][8][3] # ~(i-1) touch 0 => 0, 9 touch

    ans = 0
    for i in range(10):
        ans += dp[N][i][3]

    print(ans%1000000000)