[백준] 1562 - 계단 수 (G1)

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

1562번: 계단 수

보자마자 DP인건 알겠는데, 1시간동안 고민해도 답이 안보여서 풀이 아이디어를 보고 푼 문제이다.

이 문제는 내가 한번도 풀어본 적 없는 유형의 문제였다.

 

처음에는 '9876543210' 이라는 기본 틀에다가 앞뒤로 숫자를 붙이는 걸 고민했다.

당연히 뻘짓이었다 ㅋㅋ 12부터는 98767543210 이런식으로 기본틀 사이에 숫자가 들어갈 수 있기 때문이다.

이게 뻘짓이라는 걸 깨닫기까지 40분이 걸렸다..

 

그 다음으로는 구간DP를 떠올렸다.

길이가 i 이고 첫숫자가 j 마지막 숫자가 k 인 수의 개수

이런식으로 DP를 짜서 앞뒤로 요래조래 붙이면서 DP테이블을 채우는 걸 고민했다.

 

근데 이렇게하면 빙빙 돌고 돌아서 어떻게든 '개수'는 셀 수 있겠는데,

문제의 조건인 '0123456789 를 모두 포함한다' 라는 조건을 어떻게 체크할지 도저히 생각이 안떠올랐다.

그래서 그냥 자존심을 버리고 깔끔하게 답지를 봤다.

 

그리고 답은 내가 한번도 풀어본적 없는 비트마스킹이었다.

하지만 풀이 아이디어를 보고나니 비트마스킹을 바로 이해해서 문제에 적용할 수 있었다.

---

dp[길이][마지막수][비트값]

이렇게 dp 테이블을 설정한다.

비트값은 숫자 i 가 포함되어있으면 비트값에 2^i 을 더해준다.

 

그리고 그 i 가 포함되어있는지는 비트연산으로 확인하면 된다.

이 문제의 조건에서는 2^0 부터 2^9 까지 모두 들어있어야 하므로,

해당하는 비트값은 1023으로 유일하다.

 

dp 테이블의 크기는 최대

dp[100][10][1024] 이다.

 

dp식은 간단하다.

0, 9 같은 경계값이 아닌 일반적인 값에 대한 dp 식은

 

dp[길이 + 1][마지막수 ± 1][비트값 | (1 << (마지막수 ± 1)] += dp[길이][마지막수][비트값]

 

이다.

 

0, 9는 조건을 분기해서 더하기만 하거나, 빼기만 하면 된다.

 

# 1562 계단수
MOD = 1000000000
n = int(input())
dp = [[[0 for _ in range(1024)] for _ in range(10)] for _ in range(n+1)]
for k in range(1, 10):
    dp[1][k][1 << k] = 1

for length in range(n):
    for last in range(10):
        for bit in range(1024):
            if last < 9:
                next_bit = bit | (1 << (last + 1))
                dp[(length + 1)][last + 1][next_bit] += dp[length][last][bit]
                dp[(length + 1)][last + 1][next_bit] %= MOD

            if last > 0:
                next_bit = bit | (1 << (last - 1))
                dp[(length + 1)][last - 1][next_bit] += dp[length][last][bit]
                dp[(length + 1)][last - 1][next_bit] %= MOD

answer = 0
for last in range(10):
    answer += dp[n][last][1023]
    answer %= MOD

print(answer)