계단 수 ( 1562 번 )

1562번: 계단 수

 

---

🧠 알고리즘

• 비트마스크 + 동적 계획법(DP)

 

✔️ 동작 방식

dp[length][last_digit][bitmask]
→ 길이가 length이고, 마지막 숫자가 last_digit이며, 사용한 숫자들의 상태가 bitmask인 계단 수의 개수

• 초기값 설정 >> 길이 1에서는 1~9만 가능 → dp[1][num][1 << num] = 1
• 점화식 (이전 자리수 기반 갱신)
  • 현재 자리수 j의 비트 상태 or_num = bit | (1 << j) 계산
  • j < 9 → 이전 자리수가 j+1인 경우 가능
  • j > 0 → 이전 자리수가 j-1인 경우 가능
  • dp[i][j][or_num] += dp[i-1][j±1][bit]
• 모든 숫자(0~9)가 등장한 상태의 비트는 1023 (2^10 - 1)
• 즉, dp[n][last_digit][1023]을 모두 더한 것이 정답

---

 

🧾 코드

import sys

def _main(n):
    """
        0~9 까지 모드 등장하는 계단 수!!...
        9 8 7 6 5 4 3 2 1 0
        1 1 1 1 1 1 1 1 1 1 >> 1023
        각 수가 얼마나 나왔는지 확인하고 1023이 몇개인지 확인
        dp = [[[0] * 1024 for _ in range(10)] for _ in range(n + 1)]
    """
    answer = 0
    
    dp = [[[0] * 1024 for _ in range(10)] for _ in range(n + 1)]
    for num in range(1, 10):
        dp[1][num][1 << num] = 1

    for i in range(2, n + 1):
        for j in range(10):
            for bit in range(1024):
                or_num = bit | (1 << j)
                
                if j < 9:
                    dp[i][j][or_num] += dp[i - 1][j + 1][bit] % 1000000000
                if j > 0:
                    dp[i][j][or_num] += dp[i - 1][j - 1][bit] % 1000000000

    for idx in range(10):
        answer += dp[n][idx][-1]
        
    return answer % 1000000000
    

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

for i in range(2, n + 1) : n 길이 만큼 누적치 계산 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )