C++로 합이 n이 되는 세 숫자 찾기: 3의 배수를 피하는 방법

하나의 숫자 n이 주어졌을 때, 다음 두 조건을 동시에 만족하는 세 숫자 a, b, c를 찾는 것이 목표입니다.

• 세 숫자의 합이 n이 되어야 합니다. 즉, a + b + c = n
• 세 숫자 중 어느 것도 3의 배수가 아니어야 합니다.

예를 들어 입력이 n = 233이라면, 프로그램은 [1, 2, 230]을 출력합니다. 실제로 1 + 2 + 230 = 233이고, 세 숫자 모두 3으로 나누어 떨어지지 않으므로 조건을 만족합니다.

문제 해결 접근 방식

이 문제는 간단한 수학적 관찰만으로 O(1) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. (n - 2)를 3으로 나눈 나머지가 0이라면, 1, 2, n - 3을 반환합니다. 이 경우 n - 3은 3의 배수가 아니므로 조건을 만족합니다.
2. 그렇지 않다면(n - 2가 3의 배수가 아니라면), 1, 1, n - 2를 반환합니다. 이때 n - 2 역시 3의 배수가 아니므로 조건을 만족합니다.

즉, 큰 숫자 하나에 작은 숫자들을 더해 균형을 맞추되, 나머지 연산을 통해 3의 배수인 경우를 회피하는 전략입니다.

C++ 구현 예제

아래 코드는 위 로직을 그대로 구현한 것입니다.

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    if ((n - 2) % 3 == 0)
        cout << 1 << ", " << 2 << ", " << n - 3;
    else
        cout << 1 << ", " << 1 << ", " << n - 2;
}
int main(){
    int n = 233;
    solve(n);
}

입력

233

출력

1, 2, 230

동작 원리 상세 설명

n = 233일 때의 실행 과정을 살펴보겠습니다.

• 먼저 (n - 2) % 3을 계산합니다. (233 - 2) % 3 = 231 % 3 = 0이므로 첫 번째 분기가 실행됩니다.
• 따라서 1, 2, 그리고 n - 3인 230을 출력합니다.
• 검증: 1 + 2 + 230 = 233이며, 1 % 3 ≠ 0, 2 % 3 ≠ 0, 230 % 3 = 2 ≠ 0이므로 세 숫자 모두 3의 배수가 아닙니다.

반대로 n = 10처럼 (n - 2) % 3이 0이 아닌 경우에는 1, 1, n - 2를 출력하게 됩니다. 이처럼 단 한 번의 나머지 연산만으로 문제를 해결할 수 있어 매우 효율적입니다.