문제 개요
하나의 숫자 N이 입력으로 주어집니다. 목표는 다음 조건을 만족하는 N 이하의 모든 수 m의 개수를 찾는 것입니다. 단, N은 최대 109(십억)까지 가능합니다.
m + sum(m) + sum(sum(m)) = N
여기서 sum(m)은 m의 각 자릿수의 합을 의미합니다.
예를 들어 m이 137이라면 sum(m) = 1+3+7 = 11이고, sum(sum(m)) = sum(11) = 1+1 = 2가 됩니다.
예시로 이해하기
예시 1
입력: N = 27
출력: 조건을 만족하는 수의 개수: 3
설명: 해당하는 수들은 다음과 같습니다.
- 9 → 9 + 9 + 9 = 27
- 15 → 15 + (1+5) + (6) = 27
- 21 → 21 + (2+1) + (3) = 27
예시 2
입력: N = 81
출력: 조건을 만족하는 수의 개수: 2
설명: 해당하는 수들은 다음과 같습니다.
- 63 → 63 + (6+3) + 9 = 81
- 66 → 66 + (6+6) + (1+2) = 81
접근 방식
이 접근 방식에서는 각 숫자의 자릿수 합을 계산한 후, 그 합들을 모두 더한 값이 N과 일치하는지 확인합니다. 계산 결과가 N과 같다면 카운트를 1 증가시키고, 마지막에 카운트 값을 결과로 반환합니다.
핵심 최적화 포인트는 탐색 범위를 줄이는 것입니다. N의 최댓값이 109일 때, m의 자릿수 합은 최대 81(아홉 자리가 모두 9인 경우)이며, sum(sum(m))의 자릿수 합 역시 최대 16(예: 79 → 7+9)입니다. 즉, N-97보다 작은 수나 N보다 큰 수는 조건을 만족할 수 없으므로, N-97부터 N 사이의 숫자만 확인하면 됩니다.
- 정수 N을 입력받습니다.
- 함수 total(int num)은 하나의 숫자를 받아 그 자릿수의 합을 반환합니다.
- 자릿수 합을 누적할 res_total과 현재 자릿수를 담을 res를 선언하고 0으로 초기화합니다.
- while 루프를 사용하여 각 자릿수를 차례대로 처리합니다.
- res = num % 10으로 일의 자리 숫자를 구해 res_total에 더합니다.
- num을 10으로 나누어 다음 자릿수로 넘어갑니다.
- 루프가 끝나면 res_total을 num의 자릿수 합으로 반환합니다.
- 함수 condition(int N)은 N을 받아 m + sum(m) + sum(sum(m)) = N을 만족하는 수의 개수를 반환합니다.
- 카운트를 0으로 초기화합니다.
- for 루프를 사용해 i = N-97부터 i <= N까지 반복합니다.
- temp_1 = total(i)로 i의 자릿수 합을 구합니다.
- temp_2 = total(temp_1)로 temp_1의 자릿수 합을 구합니다.
- temp_3 = i + temp_1 + temp_2를 계산하고, 이 값이 N과 같으면 카운트를 증가시킵니다.
- for 루프가 종료되면 카운트를 결과로 반환합니다.
구현 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
int total(int num) {
int res_total = 0;
int res = 0;
while (num > 0) {
res = num % 10;
res_total = res_total + res;
num = num / 10;
}
return res_total;
}
int condition(int N) {
int count = 0;
for (int i = N - 97; i <= N; i++) {
int temp_1 = total(i);
int temp_2 = total(temp_1);
int temp_3 = i + temp_1 + temp_2;
if (temp_3 == N) {
count++;
}
}
return count;
}
int main() {
int N = 9999;
cout << "Count of numbers satisfying m + sum(m) + sum(sum(m)) = N are: " << condition(N);
return 0;
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력 결과
Count of numbers satisfying m + sum(m) + sum(sum(m)) = N are: 2
복잡도 분석
시간 복잡도: 탐색 범위가 최대 98개(N-97부터 N까지)로 고정되어 있고, 각 숫자의 자릿수 합 계산도 자릿수에 비례하므로 사실상 상수 시간(O(1))에 가깝게 동작합니다.
공간 복잡도: 추가적인 자료 구조를 사용하지 않으므로 O(1)입니다.