C++로 배열의 모든 숫자를 활용해 3으로 나누어 떨어지는 수 만드는 방법

문제 개요

이 문제에서는 하나의 배열이 주어집니다. 배열에 포함된 모든 요소들의 자릿수를 전부 사용하여 만든 숫자가 3으로 나누어 떨어지는지 확인하는 것이 과제입니다. 만들 수 있다면 "Yes", 없다면 "No"를 출력하면 됩니다.

예시로 문제 이해하기

입력: arr = {3, 5, 91}

출력: YES

설명: 배열의 숫자들을 조합해 만든 수 5193은 3으로 나누어 떨어지므로 답은 YES입니다.

해결 접근 방식

이 문제는 3의 배수 판정법을 활용하면 간단히 해결할 수 있습니다.

3의 배수 판정법: 어떤 수의 각 자릿수를 모두 더한 값이 3으로 나누어 떨어지면, 그 수 자체도 3으로 나누어 떨어집니다.

여기서 중요한 점은 숫자들을 어떤 순서로 배치하더라도 자릿수의 합은 변하지 않는다는 사실입니다. 따라서 배열 요소들의 자릿수를 모두 더한 값, 즉 배열 원소들의 합이 3의 배수인지만 확인하면 됩니다. 합이 3으로 나누어 떨어지면 YES, 그렇지 않으면 NO를 출력합니다.

C++ 구현 코드

#include <iostream>
using namespace std;

bool is3DivisibleArray(int arr[], int n) {
    int rem = 0;
    for (int i = 0; i < n; i++)
        rem = (rem + arr[i]) % 3;
    return (rem == 0);
}

int main() {
    int arr[] = { 23, 64, 87, 12, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "배열의 숫자들로 3으로 나누어 떨어지는 수 만들기: ";
    is3DivisibleArray(arr, n) ? cout << "가능합니다" : cout << "불가능합니다";
    return 0;
}

참고로, 함수 내부에서 sizeof 연산자로 배열 크기를 계산하면 배열이 포인터로 전달되어 올바른 크기를 얻을 수 없습니다. 따라서 위 코드처럼 배열 크기를 별도의 매개변수로 함께 전달하는 것이 안전하고 권장되는 방식입니다.

실행 결과

배열의 숫자들로 3으로 나누어 떨어지는 수 만들기: 가능합니다

코드 설명

is3DivisibleArray 함수는 배열의 모든 요소를 순회하며 각 값을 더한 뒤 3으로 나눈 나머지를 누적 계산합니다. 모든 요소의 합이 3의 배수라면 나머지는 0이 되고, 이 경우 함수는 true를 반환합니다. main 함수에서는 이 반환값에 따라 수를 만들 수 있는지 여부를 출력합니다.

예제 배열 {23, 64, 87, 12, 9}의 합은 195이고, 195 ÷ 3 = 65이므로 3으로 나누어 떨어집니다. 따라서 실행 결과는 "가능합니다"가 출력됩니다.