쉬운 계단 수
먼저 모든 가짓수를 세는 방법은 다음과 같다.
각 숫자의 가짓수를 파악하면서 진행해본다.
초기는 0 제외 모두 1, 0은 0이다.이다.
0123456789
0111111111
다음으로 넘어가면
0123456789
1122222221
그 다음은
0123456789
1334444432
최종 출력을 구하기 위해서는 각 가짓수 아래의 수를 모두 더하면 된다.
쉬운 계단 수 문제의 해답이다.
계단 수
근데 이번 문제는 0~9까지의 모든 수가 등장하는 계단 수의 개수를 구해야 한다.
따라서, 해당 계단 수가 어떤 숫자들을 포함하고 있는지도 구분을 해야 한다.
0~9까지의 숫자를 모두 고려할 경우 1024가지의 경우가 나오는데, 비트마스킹 기법을 활용하여 공간을 절약하면 TLE나 MLE 없이 AC받을 수 있다.
즉 쉬운 계단수 문제에서 차원을 한 단계 확장하고, 비트마스킹을 사용하여 효율적으로 인덱스를 관리하면 풀리는 문제이다.
참고링크: [알고리즘 기법] 비트필드를 이용한 DP by flaxinger
확장
그러나 훨씬 효율적으로 풀 수 있는 방법이 있는데, 어차피 0과 9를 모두 포함하는 계단수는 반드시 1~8을 포함할 수밖에 없다. 즉, 1024(2^1024)가지에서 4(2^2)가지로 줄일 수 있다.
대략 5배의 시간을 절약할 수 있다. 다만 해당 문제의 경우 1024가지를 모두 고려하더라도 AC를 받을 수 있는 문제이다.
문제
알고리즘 온라인 공부 노트