[백준 1562번] 파이썬 - 계단 수

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

 

# 조건

• 45656이란 수를 보자.
• 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
• N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.
• 0으로 시작하는 수는 계단수가 아니다.

 

입력

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

 

출력

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

 

# 접근 방법

• dp와 비트마스킹을 통하여 풀어주었다.
• DP [마지막 자리의 숫자] [비트 마스킹]
  • 비트 마스킹의 경우 현재까지 사용된 숫자를 기록해준다.
  • 2 4 5를 가지고 있다면 0000110100 -> 10진수 52로 변환
• N-1 길이의 계단 수들에서 N길이의 계단 수의 개수를 구한다(DP활용)
  • 3중 FOR문을 통해 배열을 전부 순회하며
  • 해당 수의 가장 뒷자리에 올 수 있는 수를 추가한 뒤, 이를 N길이의 2차원 배열에 추가.
• 길이에 대해 순회를 돌면서 dp_next 배열을 생성해주며 현재 길이에 대해 기록해준다
• 이후, dp 값에 복사해주며 다음 길이 체크

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
# 나머지 구할 변수  
mod = 1000000000  
  
N = int(input())  
# 0~9까지 10개의 수이므로  
# 1<<10 == 2^10 == 1024  
# 1024가 의미하는 것은 계단의 숫자를 사용했는지 안했는지에 대한 경우의수  
# 저장되는 건 그 전의 자릿수가 +1이나 -1로 끝난 것의 합을 모두 더해주는 것이다.  
dp = [[0 for _ in range(1<<10)] for _ in range(10)]  
  
# 시작자리 1로 설정해준다.  
for i in range(1, 10):  
    dp[i][1<<i] = 1  
  
# 자릿수 만큼 순회  
for i in range(1, N):  
    # 각 자릿수에서의 정보를 담을 배열  
    dp_next = [[0 for _ in range(1024)] for _ in range(10)]  
    # 0~ 9까지 순회  
    for j in range(10):  
        # 모든 비트에 대해 순회 (비트마스킹)  
        # 위의 설명처럼 1024는 계단 숫자 사용 여부에 대한 경우의 수        # 3의 경우 2 또는 4를 사용하는 경우가 있다.        
        for k in range(1024):  
            # 0과 9의 경우 앞뒤로 한칸씩 밖에 못 더해주므로 조건문을 이용하여 걸러준다.  
            if j < 9:  
                dp_next[j][k | (1 << j)] = (dp_next[j][k | (1 << j)] + dp[j+1][k]) % mod  
            if j > 0:  
                dp_next[j][k | (1 << j)] = (dp_next[j][k | (1 << j)] + dp[j - 1][k]) % mod  
  
    dp = dp_next  
  
print(sum(dp[i][1023] for i in range(10)) % mod)