BOJ 3026. V
문제 해석
세 자연수 \(X\), \(A\), \(B\), 그리고 숫자 \(0..9\)의 부분집합 \(S\)가 주어질 때, \(X\)의 배수 중에서 구간 \([A, B]\)에 속하고 모든 자리숫자가 \(S\)의 원소인 것의 개수를 세어라.
접근
\(X\)의 크기에 따라 두 가지 문제로 나눌 수 있다. \(X\)가 충분히 크면 \([A, B]\) 안에 들어가는 \(X\)의 배수들을 일일이 검사해도 충분히 빠를 것이다. 나는 \(10^5\)를 경계값으로 정했다.
이제 \(X\)가 경계값보다 작을 때를 보자. \([A, B] = [0, B] - [0, A-1]\)이므로 구간 시작이 \(0\)인 경우만 풀 수 있으면 된다. \(S\)에서 중복 가능한 숫자 \(n\)개를 뽑아 나열하여 만든 자연수 중에 그 값이 \(\mod X\)에서 \(m\)인 것의 개수를 고려하자(단, leading zero를 허용한다). 이것을 \(n, m\)에 관한 함수로 생각하면 자명하게 DP성을 띠고, \(X\)가 작아서 memoize할 수 있다.
이제 구간 \([0, A]\)에 대해 문제를 푼다면, \(A\)를 가장 높은(왼쪽) 자리부터 차례대로 본다. \(A\)의 \(i\)번째 자리 숫자를 \(A_i\)라고 할 때,
- \(S\)에 속하고 \(A_i\)보다 작은 숫자들 \(d\)에 대해 \(\overline{A_0A_1..A_{i-1}d}\)로 시작하고 \(\mod X\)에서 \(0\)인 자연수의 개수를 구해 합계에 누적한다. 이때도 역시 leading zero를 허용한다. 위에서 말한 DP 값들을 사용하면 된다.
- \(A_i\)가 \(S\)에 없으면 지금의 합계가 정답이므로(why?) 바로 종료하고, 아니면 다음 자리로 이동해 반복한다.
모든 \(A_i\)가 \(S\)에 속해서 마지막 자리까지 다 봤다면, 마지막으로 \(A\)가 \(X\)의 배수인지 검사해서 맞으면 \(1\)을 추가하면 된다.
한 가지 구현 이슈로, \(S\)에 \(0\)이 없는 경우 leading zero도 막혀서 \(A\)보다 자릿수가 적은 자연수들이 카운트에서 빠지는 문제가 있다. 내 코드에서는 solve 함수 처음에 이 개수를 먼저 세어 준다.