어떤 수가 3으로 나누어떨어지는지 확인하는 가장 간단한 방법은, 그 수의 모든 자릿수를 더한 뒤 그 합이 3으로 나누어떨어지는지 검사하는 것입니다.
이 문제에서는 정수 배열 arr[]가 주어지며, 배열에 있는 숫자들을 이어 붙여 만든 하나의 수가 3으로 나누어떨어지는지 판별해야 합니다. 나누어떨어진다면 'Yes'를, 그렇지 않다면 'No'를 출력합니다.
Input: arr[] = {45, 51, 90}
Output: Yes동작 원리
예를 들어 위 배열의 숫자들을 조합하면 945510 같은 수를 만들 수 있고, 이 수는 3으로 나누어떨어집니다. 따라서 답은 Yes입니다.
핵심 아이디어는 다음과 같습니다.
- 어떤 수를 3으로 나눈 나머지는, 그 수의 자릿수 합을 3으로 나눈 나머지와 동일합니다.
- 여러 수를 이어 붙여 만든 수의 자릿수 합은, 각 수의 자릿수 합을 모두 더한 값과 같습니다.
따라서 배열의 모든 원소를 더한 값을 3으로 나눈 나머지가 0이라면, 어떤 순서로 숫자를 조합하더라도 만들어지는 수는 반드시 3으로 나누어떨어집니다.
예제 코드
#include <stdio.h>
int main() {
int arr[] = { 45, 51, 90 };
int n = 3;
int rem = 0;
for (int i = 0; i < n; i++) {
rem = (rem + arr[i]) % 3;
}
if (rem == 0)
printf("Yes\n");
else
printf("No\n");
return 0;
}코드 설명
반복문을 돌면서 배열의 각 원소를 누적합에 더하고, 매번 3으로 나눈 나머지만 남깁니다. 이렇게 하면 값이 커져도 오버플로우 없이 효율적으로 계산할 수 있습니다. 최종 나머지가 0이면 'Yes', 아니면 'No'를 출력합니다. 시간 복잡도는 O(n)으로 매우 효율적입니다.