자릿수의 합이 4로 나누어 떨어지는 A 이상의 가장 가까운 수를 찾는 C++ 프로그램

문제 개요

숫자 A가 주어졌을 때, A보다 크거나 같은 수 중에서 '흥미로운(interesting) 수'에 해당하는 가장 가까운 수를 찾는 것이 목표입니다. 여기서 흥미로운 수란 각 자릿수의 합이 4로 나누어 떨어지는 수를 의미합니다.

예를 들어 입력이 A = 432라고 하면 출력은 435가 됩니다. 그 이유는 4 + 3 + 5 = 12이고, 12는 4로 나누어 떨어지기 때문입니다.

접근 방식

이 문제는 아주 단순한 반복 방식으로 해결할 수 있습니다. 숫자 A의 각 자릿값을 추출하여 모두 더한 뒤, 그 합을 4로 나눈 나머지가 0이 될 때까지 A를 1씩 증가시키면 됩니다.

자릿값 추출 방법은 다음과 같습니다.

• A / 1000 : 천의 자리 숫자
• A % 1000 / 100 : 백의 자리 숫자
• A % 100 / 10 : 십의 자리 숫자
• A % 10 : 일의 자리 숫자

위 방식은 최대 네 자릿수까지의 정수를 처리할 수 있으며, 자릿수의 합이 4의 배수가 될 가능성이 높기 때문에 실제 반복 횟수는 극히 적어 매우 효율적으로 동작합니다.

알고리즘 의사 코드

while (A / 1000 + A % 1000 / 100 + A % 100 / 10 + A % 10) % 4 != 0 일 동안:
    A를 1 증가
A 반환

C++ 구현 예제

다음 구현 예제를 통해 보다 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int A) {
    while ((A / 1000 + A % 1000 / 100 + A % 100 / 10 + A % 10) % 4 != 0) {
        A++;
    }
    return A;
}

int main() {
    int A = 432;
    cout << solve(A) << endl;
}

실행 결과

입력: 432

출력: 435

정리

이 알고리즘은 주어진 수부터 시작해 자릿수의 합이 4의 배수가 되는 첫 번째 수를 만날 때까지 1씩 증가시키는 직관적인 방식입니다. 자릿수의 합은 연속된 정수에서 빠르게 변화하기 때문에 최대 몇 번의 시도 안에 답을 찾을 수 있으며, 시간 복잡도 역시 사실상 상수 시간(O(1))으로 볼 수 있어 실용적인 해결책입니다.