[백준] 1562: 계단 수

문제이해

0~9까지의 숫자를 적어도 한 번씩은 거치면서 계단 수를 만들 수 있는 경우의 수를 구하는 문제다. 단, 0으로 시작할 수는 없다.

예를 들어, 10자리의 계단 수를 만들 수 있는 경우는 9876543210 밖에 없으므로 한 가지밖에 없다.

계획

0~9까지의 숫자를 적어도 한번씩 거친다는 조건이 없다고 생각하자. 행이 n, 열이 10인 2차원 배열 t가 있다고 하면, t[0]부터 t[n-1]까지 t[i][ii] (0 <= i < n, 0 <= ii < 10) 에 도달할 수 있는 경로의 수를 기록하고 ii=n-1일 때 t[n-1][0] ~ t[n-1][9] 의 수를 합하면 된다. 

다시 0~9까지의 숫자를 적어도 한번씩 거친다는 조건을 추가하면, t[i][ii]까지 방문한 열들을 계속해서 기록하면 된다. 다만, 2차원 배열에 이런 식으로 개수와 방문한 열들을 기록하면 다른 열에서 다시 t[i][ii]를 참조할 때 초기화가 되기 때문에 t[i][ii]까지 방문할 수 있는 모든 경우의 수를 나누어, 경로 1일 때는 얼마 경로 2일 때는 얼마, 이런 식으로 나누어서 기록해줘야 한다. 다만 방문을 한 번만 해도 상관없으므로 다시 방문했던 열을 방문할 때는 굳이 기록을 안 해줘도 된다.

즉, 10개의 열을 방문했는지 안했는지 기록해야 한다.방문했을 때를 1, 방문을 안 했을 때를 0으로 기록한다면.

모두 방문 했을 때 : 1111111111

모두 방문 하지 않았을 때 : 0000000000

1만 방문 했을 때 : 0000000010

이런 식으로 기록을 하게 된다.

따라서 비트로도 연산을 할 수 있게 되고, 계속해서 or연산자를 쓰면서(이미 방문했으면 상관없고, 방문 안 했으면 해당 비트수 1로 변경) 경로에 따라서 무슨 열흘을 방문했는지 기록해 주고 마지막에 가서 모두 방문했을 경우의 경로의 수만 더해주면 정답이다.

 

계획수행

import sys

n = int(sys.stdin.readline())
dp = [[[0 for _ in range(1 << 10)] for _ in range(10)] for _ in range(n)]

for i in range(n):
    for ii in range(10):
        if i == 0 and ii != 0:
            dp[0][ii][1 << ii] = 1
        for iii in range(1 << 10):
            next = [ii-1, ii+1]
            for t in next:
                if 0 <= t < 10:
                    dp[i][ii][1 << ii | iii] += dp[i-1][t][iii]		#현재 열인 ii를 or해줘 기록해 준다.

ans = 0

for i in range(10):
    ans += dp[n-1][i][(1 << 10) - 1]
    ans %= 1000000000

print(ans)

 

느낀점

처음에는 dfs를 이용하여 푸는 문제인 줄 알았다. 하지만 어떤 방식으로 해도 답이 없었고, 문제를 다시 보니까 n이 100까지밖에 안된다는 것을 발견했다. 따라서 10*100*1024는 2초 안에 순회할 수 있다는 데에서 힌트를 얻게 되었다. 처음에는 n*10*1024짜리 배열을 만들어 순회하도록 하고, 수를 들렸다는 것을 표시하려면 2**x 이런 식으로 표시했다. 그런데 비트마스킹이라는 것을 알게 되었고, 이를 더 쉽게 처리할 수 있다는 것을 알게 되었다. 집합이나 이런 곳에서도 사용할 수 있을 것 같다.