정수 N이 주어졌을 때, 홀수 자리에 있는 숫자들의 합과 짝수 자리에 있는 숫자들의 합을 각각 구해야 합니다. 예를 들어 숫자가 153654라면 odd_sum(홀수 자리 합)은 9, even_sum(짝수 자리 합)은 15가 됩니다.
이 문제는 가장 오른쪽 자릿수부터 한 자리씩 추출하면서 해결할 수 있습니다. 원래 수의 자릿수 개수가 홀수라면 마지막 자릿수는 홀수 자리에, 짝수라면 짝수 자리에 놓입니다. 한 자리를 처리할 때마다 상태를 홀수에서 짝수로, 짝수에서 홀수로 뒤집어 주면 다음 자릿수가 어느 쪽 합에 더해질지 자연스럽게 결정됩니다.
예제 코드
#include<iostream>
using namespace std;
bool isOdd(int x){
if(x % 2 == 0)
return false;
return true;
}
void getSum(int n) {
bool odd_check = isOdd(n);
int odd_sum = 0, even_sum = 0;
while (n != 0) {
if (odd_check)
odd_sum += n % 10;
else
even_sum += n % 10;
odd_check = !odd_check;
n /= 10;
}
cout << "Sum odd : " << odd_sum << endl;
cout << "Sum even : " << even_sum;
}
int main() {
int n = 153654;
getSum(n);
}
실행 결과
Sum odd : 9 Sum even : 15
코드 동작 원리
isOdd() 함수는 입력값이 홀수인지 아닌지를 판별하는 보조 함수입니다. getSum() 함수는 그 결과를 바탕으로 첫 번째로 처리할 자릿수가 홀수 자리인지 짝수 자리인지 결정한 뒤, 자릿수를 하나 처리할 때마다 odd_check 플래그를 반전시켜 홀수 자리와 짝수 자리를 번갈아가며 누적합니다.
숫자 153654를 예로 들면 다음과 같이 진행됩니다.
- 153654는 짝수이므로 첫 자릿수 4는 even_sum에 더해집니다.
- 이후 5 → odd_sum, 6 → even_sum, 3 → odd_sum, 5 → even_sum, 1 → odd_sum 순서로 번갈아 더해집니다.
- 최종적으로 odd_sum = 5 + 3 + 1 = 9, even_sum = 4 + 6 + 5 = 15가 출력됩니다.
이 알고리즘은 숫자의 모든 자릿수를 한 번씩만 확인하면 되므로, 자릿수를 d라고 할 때 시간 복잡도는 O(d)이고 추가로 필요한 메모리는 O(1)에 불과해 매우 효율적입니다.