BOJ 1040. 정수
문제 해석
\(0 \cdots 9\) 숫자 중에 정확히 \(K\)종류만 사용되는 자연수 중에서, \(N\) 이상이면서 최소인 것을 찾아라.
접근
찾으려고 하는 자연수를 \(M\)이라고 하고, \(N\)과 \(M\)이 각각 \(l_N\)자리, \(l_M\)자리 자연수라고 하자.
먼저 \(l_M > l_N\)인 경우부터 생각해보자. \(K\)가 \(l_N\)보다 크거나, \(l_N\)자리 자연수 중에서 \(M\)을 찾지 못했을 때 여기에 해당할 것이다. 그러면 \(l_M = \max(l_N + 1, K)\)이고, \(l_M\)자리 수 중에서 숫자 \(K\)종류를 사용하는 제일 작은 것을 구하면 된다. 예를 들어 \(l_M = 8, K = 5\)라면 \(M = 10000234\)가 되는 식이다.
이제 \(l_M = l_N\)인 경우를 보자. \(N\)의 맨 왼쪽 자리(\(i=0\))부터 보면서 차례대로 보는 backtracking 같은 방식을 생각할 수 있지만, 이렇게만 구현하면 너무 오래 걸리고 state를 적당히 잡아서 DP로 만들어야 한다.
\(i\)번째 자리를 보고 있을 때 선택지에 영향을 주는 정보가 무엇인지 생각해 보자.
- 마지막 자리까지 갔을 때 숫자를 정확히 \(K\)종류 사용했는지 확인해야 할 테니 \((i-1)\)번째 자리까지 어떤 숫자들을 쓰고 있는지 관리해야 한다.
- \(N\) 이상인 수들만 봐야 하므로 \(0 \cdots (i-1)\)번째 자리들이 모두 \(N\)에서와 일치하는지(tight) 관리해야 한다. 이것이
true면 \(N\)의 \(i\)번째 자리 숫자 이상만 고를 수 있고,false면 이미 \(N\)보다 커진 상황이니 \(0 \cdots 9\) 모두 사용 가능하다.
따라서 <현재 보고 있는 자리, 이전까지 사용한 숫자들을 기록한 bitmask, tight 여부>를 묶어서 state로 정의하고, 이미 방문한 적 있는 state는 즉시 “불가능”으로 판단하고 건너뛰면 연산량을 대폭 줄일 수 있다.