문제 개요
이 글에서는 n개의 숫자로 이루어진 배열이 주어졌을 때, 배열의 모든 요소를 이어 붙여 만든 하나의 정수가 3으로 나누어 떨어지는지 확인하는 방법을 다룹니다.
예를 들어 배열 요소가 {15, 24, 23, 13}이라면, 이 요소들을 차례대로 연결하여 15242313이라는 정수를 만들 수 있습니다. 이 수는 3으로 나누어 떨어집니다.
핵심 아이디어
거대한 숫자를 직접 만들 필요는 없습니다. 수학적으로 잘 알려진 성질에 따르면, 어떤 수가 3으로 나누어 떨어지려면 그 수의 각 자릿수의 합이 3으로 나누어 떨어져야 합니다.
배열 요소들을 이어 붙인 수의 자릿수 합은 결국 각 배열 요소들의 자릿수 합과 같으므로, 배열의 모든 요소를 더한 값이 3으로 나누어 떨어지는지만 확인하면 됩니다. 이렇게 하면 오버플로우 걱정 없이 효율적으로 문제를 해결할 수 있습니다.
알고리즘
Begin
rem := 0
for each element e in arr, do
rem := (rem + e) mod 3
done
if rem is 0, then
return true
end if
return false
End알고리즘의 동작 과정은 다음과 같습니다.
- 나머지를 저장할 변수 rem을 0으로 초기화합니다.
- 배열의 각 요소 e에 대해 rem := (rem + e) mod 3 을 계산하며 누적합니다.
- 모든 요소를 처리한 후 rem이 0이면 true(나누어 떨어짐), 아니면 false(나누어 떨어지지 않음)를 반환합니다.
C++ 구현 예제
#include<iostream>
#define MAX 4
using namespace std;
bool checkDivThree(int arr[], int n){
int rem = 0;
for(int i = 0; i<n; i++){
rem = (rem + arr[i]) % 3;
}
if(rem == 0){
return true;
}
return false;
}
main() {
int arr[] = {15, 24, 23, 13};
int n = sizeof(arr)/sizeof(arr[0]);
if(checkDivThree(arr, n)){
cout << "Divisible";
}else{
cout << "Not Divisible";
}
}실행 결과
Divisible
동작 원리 살펴보기
위 예제에서 배열 {15, 24, 23, 13}의 각 요소를 순서대로 처리해 보겠습니다.
- 초기 rem = 0
- (0 + 15) % 3 = 0
- (0 + 24) % 3 = 0
- (0 + 23) % 3 = 2
- (2 + 13) % 3 = 0
최종 rem이 0이므로, 배열 요소로 만든 수 15242313은 3으로 나누어 떨어진다는 것을 확인할 수 있습니다. 실제로 15 + 24 + 23 + 13 = 75이며, 75는 3으로 나누어 떨어집니다.
이 방법의 시간 복잡도는 O(n)으로, 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다. 또한 각 단계마다 모듈로 연산을 적용하므로, 배열 요소가 아무리 커도 오버플로우 없이 안전하게 처리할 수 있다는 장점이 있습니다.