두 수 L과 R이 주어져 범위 [L, R]을 정의합니다. 목표는 이 범위 안의 수들 중 짝수이면서 동시에 각 자릿수의 합이 3으로 나누어떨어지는 모든 수의 개수를 구하는 것입니다.
해결 방법은 간단합니다. L부터 R 사이의 모든 짝수에 대해 자릿수의 합을 계산하고, 그 합을 3으로 나눈 나머지가 0이면 카운트를 1씩 증가시키면 됩니다.
예제로 이해하기
입력 — L=10, R=20
출력 — 범위 [L, R]에서 자릿수의 합이 3으로 나누어떨어지는 짝수의 개수: 2
설명 — 10과 20 사이의 짝수는 10, 12, 14, 16, 18, 20입니다. 이 중 자릿수의 합이 3으로 나누어떨어지는 수는 12(1+2=3)와 18(1+8=9), 총 2개입니다.
입력 — L=100, R=108
출력 — 범위 [L, R]에서 자릿수의 합이 3으로 나누어떨어지는 짝수의 개수: 2
설명 — 100과 108 사이의 짝수는 100, 102, 104, 106, 108입니다. 이 중 자릿수의 합이 3으로 나누어떨어지는 수는 102(1+0+2=3)와 108(1+0+8=9), 총 2개입니다.
알고리즘 접근 방법
- 범위를 정의하기 위해 first와 last 변수를 사용합니다.
- Digit_sum(int num) 함수는 입력받은 수의 자릿수 합을 계산해 반환합니다.
- while 반복문으로 num이 0이 아닌 동안 num % 10(일의 자리 숫자)을 total에 더합니다.
- num을 10으로 나누어 한 자리씩 줄여가며 위 과정을 반복합니다.
- 반복이 끝나면 total에는 모든 자릿수의 합이 저장됩니다.
- divisible_3(int first, int last) 함수는 범위를 받아 조건을 만족하는 짝수의 개수를 반환합니다.
- i를 first부터 last까지 반복하면서 해당 수가 짝수인지 확인합니다(i % 2 == 0).
- 짝수라면 Digit_sum(i)를 호출해 자릿수의 합을 구하고, 그 값이 3으로 나누어떨어지면 count를 증가시킵니다.
- 반복문이 종료되면 count를 결과로 반환합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
// 자릿수의 합을 계산하는 함수
int Digit_sum(int num){
int total = 0;
while (num != 0){
total += num % 10; // 일의 자리 숫자를 더함
num = num / 10; // 마지막 자리 제거
}
return total;
}
// 조건을 만족하는 짝수의 개수를 세는 함수
int divisible_3(int first, int last){
int count = 0;
for (int i = first; i <= last; i++){
if (i % 2 == 0 && Digit_sum(i) % 3 == 0){
count++;
}
}
return count;
}
int main(){
int first = 300, last = 500;
cout << "[300, 500] 범위에서 자릿수의 합이 3으로 나누어떨어지는 짝수의 개수: " << divisible_3(first, last);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
[300, 500] 범위에서 자릿수의 합이 3으로 나누어떨어지는 짝수의 개수: 34
보너스: 수학적 성질을 활용한 O(1) 최적화
어떤 수의 자릿수 합이 3으로 나누어떨어진다는 것은 그 수 자체가 3의 배수라는 것과 같습니다. 따라서 '짝수이면서 자릿수의 합이 3으로 나누어떨어지는 수'는 결국 6의 배수와 동일합니다. 이 성질을 이용하면 반복문 없이 등차수열 공식으로 답을 바로 구할 수 있습니다.
// 6의 배수 개수를 직접 계산하는 최적화 함수
int divisible_3_fast(int first, int last){
int start = ((first + 5) / 6) * 6; // first 이상인 가장 작은 6의 배수
if (start > last) return 0;
return (last - start) / 6 + 1;
}
예를 들어 [300, 500] 범위에서 6의 배수는 300부터 498까지 존재하며, (498 − 300) / 6 + 1 = 34개로 기존 방식과 동일한 결과를 훨씬 빠르게 얻을 수 있습니다. 시간 복잡도는 O(N × D)(N은 범위 크기, D는 자릿수)에서 O(1)로 개선됩니다.