C++로 3의 배수이면서 6의 배수가 아닌 순열 찾기

문제 정의

숫자 n이 주어졌을 때, 이 숫자의 자릿수를 재배열하여 만들 수 있는 순열(permutation) 중에서 3으로는 나누어떨어지지만 6으로는 나누어떨어지지 않는 값을 찾아야 합니다. 만약 그런 값을 만들 수 없다면 -1을 반환합니다.

예를 들어 n이 336이라면, 자릿수를 바꾼 363이 정답이 될 수 있습니다. 363은 각 자릿수의 합이 12이므로 3의 배수이고, 일의 자리가 3으로 홀수이기 때문에 6의 배수는 아닙니다.

해결 아이디어

어떤 수가 6으로 나누어떨어진다는 것은 그 수가 3과 2로 모두 나누어떨어진다는 뜻입니다. 즉, 3의 배수인 짝수는 반드시 6의 배수입니다.

여기서 한 가지 중요한 성질을 활용할 수 있습니다. 자릿수의 순서를 아무리 바꿔도 각 자릿수의 합은 변하지 않으므로 3의 배수 여부는 그대로 유지됩니다. 따라서 3의 배수이면서 짝수인 수의 자릿수를 교환하여 일의 자리를 홀수로 만들기만 하면, 조건을 만족하는 순열을 얻을 수 있습니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
int findNumber(int n) {
    int digit_count = ceil(log10(n));
    for (int i = 0; i < digit_count; i++) {
        if (n % 2 != 0) {
            return n;
        } else {
            n = (n / 10) + (n % 10) * pow(10, digit_count - i - 1);
            continue;
        }
    }
    return -1;
}
int main() {
    int n = 132;
    cout <<"The permutation of "<<n << " that is divisible by 3 but not by 6 is:"<< findNumber(n);
}

실행 결과

The permutation of 132 that is divisible by 3 but not by 6 is:213

코드 동작 방식

• 자릿수 계산: log10()과 ceil() 함수를 이용해 숫자 n의 자릿수를 구합니다.
• 홀수 판별: n이 이미 홀수라면(n % 2 != 0), 3의 배수이면서 6의 배수가 아니므로 그대로 반환합니다.
• 자릿수 회전: n이 짝수라면 마지막 자릿수를 떼어 내어 앞쪽으로 이동시키는 회전을 수행합니다. 예를 들어 132는 213으로 바뀌며, 이 시점에서 홀수가 되므로 곧바로 반환됩니다.
• 실패 처리: 모든 자릿수가 짝수라면 어떻게 배치하더라도 홀수를 만들 수 없으므로 -1을 반환합니다.

정리

이 문제의 핵심은 "6의 배수 = 3의 배수이면서 짝수"라는 성질입니다. 자릿수를 재배열해도 3의 배수 여부는 변하지 않으므로, 짝수인 입력값의 자릿수를 회전시켜 홀수 형태의 순열을 찾으면 됩니다. 단, 모든 자릿수가 짝수인 경우에는 조건을 만족하는 순열이 존재하지 않으므로 -1을 반환해야 한다는 점에 유의하시기 바랍니다.