문제 개요
숫자 N이 주어졌다고 가정해 봅시다. 양의 정수 x에 대해 정의되는 함수 gcdSum(x)은 그 정수 자신과 자릿수 합의 최대공약수(gcd)를 의미합니다. 우리가 구해야 할 것은 gcdSum(x) > 1을 만족하는 가장 작은 정수 x(x ≥ n)입니다.
예를 들어 입력이 N = 31이라면 출력은 33이 됩니다. 31과 자릿수 합 (3+1)=4의 최대공약수는 1이고, 32와 (3+2)=5의 최대공약수 역시 1입니다. 하지만 33과 (3+3)=6의 최대공약수는 3으로 1보다 크기 때문에 조건을 만족하는 첫 번째 수는 33이 됩니다.
접근 방법
핵심 아이디어는 간단합니다. n부터 시작해 하나씩 값을 늘려가며 각 수에 대해 gcdSum을 계산하고, 처음으로 1보다 커지는 지점을 반환하면 됩니다.
그렇다면 몇 개의 수까지 확인하면 충분할까요? 다행히 세 개의 연속된 정수 중에는 반드시 조건을 만족하는 수가 존재합니다. 어떤 수가 3으로 나누어떨어지면 그 수의 자릿수 합도 반드시 3으로 나누어떨어진다는 성질 때문입니다. 따라서 n, n+1, n+2 중 하나는 반드시 3의 배수이며, 해당 수의 gcdSum은 최소 3 이상이 됩니다. 즉, 탐색 범위를 n부터 n+2까지만 확인하면 항상 답을 찾을 수 있습니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다.
for initialize i := n, when i <= n + 2, update (increase i by 1), do:
jml := 0
x := i
while x > 0, do:
jml := jml + x mod 10
x := x / 10
if gcd of i and jml is not equal to 1, then:
return i
return 0
각 단계를 요약하면 다음과 같습니다.
- n부터 n+2까지 차례대로 순회합니다.
- 현재 수의 모든 자릿수를 더해 자릿수 합을 구합니다.
- 현재 수와 자릿수 합의 최대공약수가 1이 아니라면 해당 수를 정답으로 반환합니다.
예제 코드 (C++)
더 나은 이해를 위해 다음 C++ 구현 예시를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n) {
for (long i = n; i <= n + 2; i++) {
long jml = 0;
long x = i;
while (x > 0) {
jml += x % 10;
x /= 10;
}
if (__gcd(i, jml) != 1) {
return i;
}
}
return 0;
}
int main() {
int N = 31;
cout << solve(N) << endl;
}
입력
31
출력
33
복잡도 분석
탐색 범위가 최대 3개의 수로 제한되고, 각 수의 자릿수 계산은 O(log n) 시간이 걸리므로 전체 시간 복잡도는 O(log n)입니다. 추가적인 메모리 사용 없이 상수 공간만 필요하므로 매우 효율적인 해법입니다.