처음에는 브루트 포스 알고리즘으로 풀어보려고 했다. 숫자를 사용할때마다 check에서 각 자릿수의 개수를 +1 해주고, 재귀깊이가 10이 되면 모든 숫자가 사용되었는지 확인하는 코드이다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
N = int(input())
result = 0
check = [0]*10
def stair(last,cnt):
global result
if cnt == N:
success = True
for i in range(10):
if check[i] == 0:
success = False
if success:
result += 1
return
for i in [-1,1]:
now = last+i
if 9>=now>=0:
check[now] += 1
stair(now,cnt+1)
check[now] -= 1
for i in range(1,10):
check[i] += 1
stair(i,1)
check[i] -= 1
print(result)하지만 제출하자마자 시간초과가 발생하였다.
당연했다. 왜냐하면 모든 경우의 수를 계산하려면 시간복잡도가 O(2^N)이기 때문이다.
그래서 어떻게 풀어야할까 고민하다가 DP를 이용하면 되겠다 생각했다.
그랬더니 무려 44ms만에 코드가 통과되었다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
mod = 1000000000
N = int(input())
def stair(M,m):
DP = [[[0]*10 for i in range(10)] for i in range(N+1)]
for i in range(10):
DP[1][i][i] = 1
for n in range(1,N+1):
for start in range(m,M+1):
for end in range(m,M+1):
if start>m:
DP[n][start][end] += DP[n-1][start-1][end]
if start<M:
DP[n][start][end] += DP[n-1][start+1][end]
result = 0
for i in range(1,10):
result += sum(DP[N][i])%mod
return result%mod
print((stair(9,0)-stair(9,1)-stair(8,0)+stair(8,1))%mod)계단수 알고리즘을 요약하면 다음과 같다.
1. 길이, 맨 첫자릿수, 맨 끝자릿수로 이루어진 3차원 DP를 만든다.
2. 현 자릿수에서 숫자를 하나 더 붙인다는 생각으로 점화식을 짠다.
3. 맨 첫자릿수가 0으로 시작하는 값을 제외한 나머지 DP 최종값의 합을 출력한다.
일단 이것이 기본 알고리즘이다.
이때 중요한것은 0부터 9까지가 모두 쓰였는지를 확인하는 작업이 필요한데, 나는 이것을 가장 큰수와 가장 작은수를 0과 9로 정해놓는 것이 아닌 m과 M인 함수로 만들어서 해결하였다.
(0~9까지 사용하는 경우의 수) - (0~8까지 사용하는 경우의 수) - (1~9까지 사용하는 경우의 수) + (1~8까지 사용하는 경우의 수) = (0~9까지 모든 수를 사용한 경우의 수)
간단한 집합문제이다.
다른 풀이를 보니 비트마스킹? 이란 알고리즘을 이용했다고 하는데, 일단 내 방법보다는 느린 것 같다.
하지만 이후 다른 문제를 해결하는 과정에서 쓰일지도 모르는 알고리즘이기 때문에 알아두어야 할 필요는 있을 것이다.
오늘의 교훈) 비트마스킹에 대해서 알아보자