암스트롱 수(Armstrong Number)는 각 자릿수를 분리한 뒤 n제곱하여 모두 더한 합이 원래의 수와 같아지는 정수를 말합니다. 이를 수식으로 표현하면 다음과 같습니다.
abcd... = an + bn + cn + dn + ...
3자리 암스트롱 수의 예시
3자리 암스트롱 수의 경우, 각 자릿수를 세제곱한 값들의 합이 그 수 자신과 같습니다. 대표적인 예로 153을 들 수 있습니다.
153 = 13 + 53 + 33 = 1 + 125 + 27 = 153 // 153은 암스트롱 수입니다.
두 정수 사이의 암스트롱 수 구하기
예를 들어 999부터 9999 사이의 암스트롱 수를 구하면 다음과 같은 결과가 나옵니다.
입력: 두 개의 숫자(범위) 입력: 999 9999 출력: 999과 9999 사이의 암스트롱 수: 1634 8208 9474
결과 설명
1634가 암스트롱 수인 이유를 살펴보겠습니다. 1634는 4자리 수이므로 각 자릿수를 네제곱하여 더합니다.
1634 = 14 + 64 + 34 + 44 = 1 + 1296 + 81 + 256 = 1634
참고로 일반적으로 정의에 따르면 n자리 수일 때 각 자릿수를 n제곱하게 되며, 위 예시에서 1634는 4자리 수이므로 네제곱의 합으로 계산하는 것이 정확합니다.
알고리즘 접근 방법
구현 방법은 매우 간단합니다. 주어진 범위 내의 모든 숫자를 하나씩 순회하면서 다음 과정을 수행합니다.
1. 현재 숫자의 자릿수 개수를 셉니다. 이 값을 n이라고 합니다.
2. 각 자릿수를 n제곱한 값들을 모두 더합니다.
3. 그 합이 원래의 수와 같다면 해당 숫자를 출력합니다.
C 언어 구현 예제
아래는 C 언어로 작성한 전체 코드입니다. 100부터 400 사이의 암스트롱 수를 찾는 예제입니다.
#include <stdio.h>
#include <math.h>
int main() {
int low = 100;
int high = 400;
printf("%d과 %d 사이의 암스트롱 수는 다음과 같습니다 \n",low,high);
for (int i = low+1; i < high; ++i) {
int x = i;
int n = 0;
while (x != 0) {
x /= 10;
++n;
}
int pow_sum = 0;
x = i;
while (x != 0) {
int digit = x % 10;
pow_sum += pow(digit, n);
x /= 10;
}
if (pow_sum == i)
printf("%d ", i);
}
printf("\n");
return 0;
}코드 동작 원리
코드의 핵심 로직을 단계별로 살펴보면 다음과 같습니다.
첫 번째 while 루프: 숫자를 10으로 나누는 연산을 반복하면서 자릿수(n)를 계산합니다. 예를 들어 153이라면 10으로 나누기를 세 번 수행하므로 n = 3이 됩니다.
두 번째 while 루프: x % 10 연산으로 마지막 자릿수를 추출하고, pow() 함수를 사용해 n제곱한 후 누적합(pow_sum)에 더합니다. 그리고 x /= 10으로 다음 자릿수로 이동합니다.
최종 비교: 모든 자릿수의 거듭제곱 합(pow_sum)이 원래 수(i)와 같으면 그 수를 화면에 출력합니다.
이 알고리즘의 시간 복잡도는 범위 내 숫자 개수에 자릿수 계산 시간을 곱한 형태로, 주어진 범위가 크지 않다면 충분히 효율적으로 동작합니다.