C++로 숫자가 연속된 세 정수의 합으로 표현 가능한지 확인하는 방법

개요

이 글에서는 어떤 숫자가 연속된 세 정수의 합으로 표현될 수 있는지 확인하는 방법을 알아보겠습니다. 예를 들어 숫자 27은 8 + 9 + 10처럼 연속된 세 정수의 합으로 나타낼 수 있습니다.

문제 해결 접근 방법

이 문제는 두 가지 방식으로 해결할 수 있습니다.

1. 단순 탐색(Naïve) 방법

첫 번째 방법은 가능한 모든 경우를 하나씩 검사하는 단순한 방식입니다. i + (i + 1) + (i + 2)의 값이 주어진 숫자와 같아지는 정수 i가 존재하는지 차례대로 확인합니다.

2. 수학적 접근(효율적인 방법)

훨씬 더 효율적인 방법은 숫자가 3으로 나누어 떨어지는지만 확인하는 것입니다. 어떤 수 x가 연속된 세 정수 (y - 1), y, (y + 1)의 합으로 표현된다면 다음과 같이 정리할 수 있습니다.

x = (y - 1) + y + (y + 1) = 3y

따라서 x는 반드시 3의 배수여야 합니다. 즉, 주어진 숫자가 3으로 나누어 떨어지면 연속된 세 정수의 합으로 표현할 수 있고, 그렇지 않다면 불가능합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
bool hasThreeNums(int n) {
    if(n % 3 == 0){
        return true;
    }
    return false;
}
int main() {
    int num = 27;
    if(hasThreeNums(num)){
        cout << "Can be represented";
    }else{
        cout << "Cannot be presented";
    }
}

실행 결과

Can be represented

위 예제에서 입력값 27은 3으로 나누어 떨어지므로 "Can be represented"가 출력되며, 이는 27이 8 + 9 + 10으로 표현 가능함을 의미합니다.