Baekjoon 1562. 계단 수 / Python

1562. 계단 수

난이도 : 골드 1
소요 시간 : 20분
날짜 : 2024.12.21
언어 : 파이썬
알고리즘 유형 : 비트마스킹, 비트집합, 다이나믹프로그래밍

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 계단수 = 인접 한 수 끼리의 차이가 1은 수
2. 길이 N인 계단 수의 개수를 구하는 문제
3. 0으로 시작하면 안된다.

2. 해결 방식

1. 비트와 dp를 사용한다.
2. dp[i][j][k]의 값은 i자리, j로 끝나는, 비트 k 를 가진 수 이다.
3. 이 때, 비트 k라는 것은, 10자리의 비트로써, 0부터 9까지의 수를 체크하는 역할이다. -> 모두 1인 1111111111이 되어야 계단수의 조건을 만족한다.

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline

masking = 1 << 10
div = 10 ** 9

def sol(n: int):
    dp = [[[0] * masking for _ in range(10)] for _ in range(n + 1)]

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

    for i in range(1, n):
        for j in range(10):
            for k in range(masking):
                if j > 0:
                    dp[i + 1][j - 1][k | (1 << (j - 1))] += dp[i][j][k]
                    dp[i + 1][j - 1][k | (1 << (j - 1))] %= div
                if j < 9:
                    dp[i + 1][j + 1][k | (1 << (j + 1))] += dp[i][j][k]
                    dp[i + 1][j + 1][k | (1 << (j + 1))] %= div

    res = 0
    for i in range(10):
        res += dp[n][i][masking - 1]
        res %= div

    print(res)

sol(int(input()))