C++에서 N 이하, 모든 자릿수가 짝수인 가장 큰 수 찾기

개요

이 튜토리얼에서는 주어진 숫자 n보다 크지 않으면서, 모든 자릿수가 짝수로만 이루어진 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.

문제 해결 접근 방식

가장 직관적인 방법인 완전 탐색으로 문제를 해결할 수 있으며, 전체 흐름은 다음과 같습니다.

• 숫자 n을 초기화합니다.
• i = n부터 시작하는 반복문을 작성합니다.
  • 현재 숫자의 각 자릿수가 모두 짝수인지 확인합니다.
  • 조건을 만족하면 해당 숫자를 반환합니다.
  • 조건을 만족하지 않으면 i를 1 감소시킨 후 다시 검사합니다.

예제 코드

위 접근 방식을 그대로 구현한 코드입니다.

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

int allDigitsEven(int n) {
    while (n) {
        if ((n % 10) % 2) {
            return 0;
        }
        n /= 10;
    }
    return 1;
}

int findLargestEvenNumber(int n) {
    int i = n;
    while (true) {
        if (allDigitsEven(i)) {
            return i;
        }
        i--;
    }
}

int main() {
    int N = 43;
    cout << findLargestEvenNumber(N) << endl;
    return 0;
}

코드 설명

allDigitsEven 함수는 10으로 나눈 나머지를 이용해 일의 자리부터 차례대로 검사합니다. 홀수 자릿수가 하나라도 발견되면 0을 반환하고, 모든 자릿수가 짝수이면 1을 반환합니다.

findLargestEvenNumber 함수는 n부터 시작해 위 조건을 만족하는 첫 번째 수를 찾을 때까지 1씩 감소시키며 탐색합니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

42

N이 43일 때, 43에는 홀수인 자릿수 3이 포함되어 있어 조건을 만족하지 않습니다. 바로 아래 수인 42는 4와 2가 모두 짝수이므로 정답이 됩니다.

마무리

이번 글에서는 완전 탐색 기법으로 N 이하에서 모든 자릿수가 짝수인 가장 큰 수를 구해 보았습니다. 이 방법은 구현이 매우 간단하지만, 최악의 경우 O(n) 시간이 소요될 수 있습니다. 입력 범위가 크다면 각 자릿수를 직접 조정하는 그리디 방식으로 최적화할 수 있다는 점도 기억해 두세요. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.