C++에서 자릿수의 합이 n이 되는 최소 행운의 숫자 찾기

문제 설명

행운의 숫자(Lucky Number)란 십진수 표현에서 오직 행운의 자릿수인 4와 7로만 이루어진 양의 정수를 의미합니다. 이 문제의 목표는 자릿수의 합이 정확히 n이 되는 최소의 행운의 숫자를 찾는 것입니다.

예시

예를 들어 합계(sum)가 22라면 정답은 4477입니다. 4 + 4 + 7 + 7 = 22이므로 자릿수의 합 조건을 만족하며, 가능한 조합 중에서 가장 작은 수입니다.

알고리즘 접근 방식

1. 합계가 4의 배수이면, 결과는 모두 4로 구성됩니다.
2. 합계가 7의 배수이면, 결과는 모두 7로 구성됩니다.
3. 합계가 4 또는 7의 배수가 아니라면, 두 숫자 중 하나를 반복해서 빼다 보면 다른 하나의 배수가 되는 시점에 도달합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
void luckyNumber(int sum) {
    int a, b;
    a = b = 0;
    while (sum > 0) {
        if (sum % 7 == 0) {
            ++b;
            sum = sum - 7;
        } else
        if (sum % 4 == 0) {
            ++a;
            sum = sum - 4;
        } else {
            ++a;
            sum = sum - 4;
        }
    }
    cout << "Answer = ";
    if (sum < 0) {
        cout << "-1\n" << endl;
        return;
    }
    for (int i = 0; i < a; ++i) {
        cout << "4";
    }
    for (int i = 0; i < b; ++i) {
        cout << "7";
    }
    cout << endl;
}
int main() {
    int sum = 22;
    luckyNumber(sum);
    return 0;
}

코드 동작 원리

이 코드는 그리디(Greedy) 기법으로 동작합니다. 남은 합계가 7로 나누어떨어지면 7을 하나 사용하고(b 증가), 그렇지 않으면 4를 하나 사용(a 증가)하며 합계에서 해당 값을 차감합니다. 이 과정을 합계가 0 이하가 될 때까지 반복합니다.

모든 차감이 끝난 후 합계가 음수라면, 주어진 합으로는 행운의 숫자를 만들 수 없다는 뜻이므로 -1을 출력합니다. 성공한 경우에는 4를 먼저, 그다음 7을 출력하는데, 오름차순으로 배치해야 같은 자릿수 구성 중에서 가장 작은 수가 되기 때문입니다.

출력 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Answer = 4477