✓

태그:

CLASS 5

길이가 N인 계단 수 중 0부터 9까지 모든 숫자가 쓰인 계단 수의 개수를 10⁹로 나눈 나머지를 출력하는 문제입니다. 여기서 계단 수는 인접한 숫자의 차이가 항상 1인 숫자입니다. 예를 들어, 101234565678789는 0부터 9까지 모든 숫자가 쓰인 계단 수입니다. 이러한 계단 수를 구하는 방법은 naive하게 DFS를 사용하는 방법도 있겠지만, 그 경우 $O(2^N)$ 정도의 시간 복잡도를 예상할 수 있겠습니다. 최대로 주어지는 N의 값이 100이라고 했으므로 시간 초과가 나기 충분한 시간 복잡도입니다. 대신 DP를 사용하여 상수가 조금 많이 크긴 하지만 $O(N)$으로 끝내는 방법이 있습니다. 계단 수 중 마지막 숫자와 지금까지 사용된 숫자를 비트필드 형태로 DP 배열의 인덱스로 사용하는 것입니다. 그 구조와 관계식은 아래와 같을 것입니다.

dp[10][1 << 10]; # dp[i][j]: 계단 수 중 마지막 숫자가 i이며 사용된 숫자는 j에 비트필드 형태로 저장

new_dp[i - 1][j | (1 << (i - 1))] += dp[i][j] if valid
new_dp[i - 1][j | (1 << (i - 1))] %= 1e9
new_dp[i + 1][j | (1 << (i + 1))] += dp[i][j] if valid
new_dp[i + 1][j | (1 << (i + 1))] %= 1e9

이 관계식을 주어진 N에 맞게 적용 후 모든 숫자를 사용한 계단 수만 추려서 답을 구하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-09 22:56:24

---