[python] 백준 1562 계단 수

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

1562번: 계단 수

 

개념 정리

비트 연산자

• AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환
• OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환
• XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환

• 왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다.
• 오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. 

1011 & 1111 # 1011
1011 | 1111 # 1111
1011 ^ 1111 # 0100
00001010 << 2 # 101000
00001010 >> 2 # 000010

문제 해결

• 먼저 비트마스크를 알아야 한다.
• dp[i][k]는 마지막 숫자가 i이고 0~9 숫자 유무를1,0으로 나타낸k의 개수를 나타낸다.

CODE

import sys
input = sys.stdin.readline
mod = 1000000000
M = (1<<10)-1
n = int(input())
dp = [[0]*(M+1) for _ in range(10)]
for i in range(1,10):
    dp[i][1<<i] = 1
for _ in range(2,n+1):
    next_dp = [[0]*(M+1) for _ in range(10)]
    for i in range(10):
        for j in range(M+1):
            if i>0:
                next_dp[i][j|(1<<i)] = (
                    next_dp[i][j|(1<<i)] + dp[i-1][j])%mod #j에 num추가
            if i<9:
                next_dp[i][j|(1<<i)] = (
                    next_dp[i][j|(1<<i)] + dp[i+1][j])%mod
    dp = next_dp
answer = sum(dp[i][M] for i in range(10))%mod
print(answer)