문제 개요
숫자로만 이루어진 문자열 S와 하나의 정수 M이 주어졌다고 가정해 봅시다. S에서 가장 큰 자릿수를 d라고 할 때, d+1 이상의 정수 n을 밑(base)으로 선택하여 S를 n진법 수로 해석했을 때, 그 결과값이 M보다 크지 않은 경우가 총 몇 가지인지 구하는 것이 이 문제의 목표입니다.
예를 들어 S = "999", M = 1500이라고 하겠습니다. S를 10진수로 해석하면 999, 11진수로 해석하면 1197, 12진수로 해석하면 1413이 됩니다. 이 세 값이 바로 M(=1500) 이하가 되는 유일한 경우이므로, 정답은 3입니다.
접근 방법
밑수가 커질수록 S를 해당 진법으로 해석한 값도 커진다는 성질이 있습니다. 이 단조 증가하는 특성 덕분에 이분 탐색(binary search)을 활용하면 효율적으로 문제를 해결할 수 있습니다. 알고리즘의 전체 흐름은 다음과 같습니다.
S의 길이가 1이라면:
S의 값 <= M이면:
return 1
그렇지 않으면:
return 0
d := 0
S의 각 문자 c에 대해:
d := d와 (c - '0') 중 최댓값
left := d
right := M + 1
right - left > 1인 동안 반복:
mid := (left + right) / 2
v := 0
S의 각 문자 c에 대해:
if v > M / mid, then:
v := M + 1 (오버플로 방지)
그렇지 않으면:
v := v * mid + (c - '0')
if v <= M, then:
left := mid
그렇지 않으면:
right := mid
return left - d
여기서 주목할 점은 탐색 범위의 하한을 d로 설정한다는 것입니다. 어떤 진법에서든 각 자릿수는 밑보다 작아야 하므로, 유효한 밑수는 최소 d+1부터 시작하기 때문입니다. 또한 계산 도중 값이 M을 초과하면 즉시 M+1로 설정하여 오버플로우를 방지하고 불필요한 연산을 줄입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(string S, int M){
if (S.size() == 1){
if (stoi(S) <= M)
return 1;
else
return 0;
}
int d = 0;
for (char c : S)
d = max(d, int(c - '0'));
long left = d;
long right = M + 1;
while (right - left > 1){
long mid = (left + right) / 2;
long v = 0;
for (char c : S){
if (v > M / mid)
v = M + 1;
else
v = v * mid + (c - '0');
}
if (v <= M)
left = mid;
else
right = mid;
}
return left - d;
}
int main(){
string S = "999";
int M = 1500;
cout << solve(S, M) << endl;
}
입력
"999", 1500
출력
3
복잡도 분석
이 알고리즘의 시간 복잡도는 O(|S| × log M)입니다. 이분 탐색이 log M번 반복되고, 각 반복마다 문자열 S의 모든 문자를 한 번씩 순회하기 때문입니다. 문자열 길이나 M의 크기가 커져도 충분히 빠르게 동작하는 효율적인 방식입니다.