C++로 n을 표현하는 데 필요한 최소 이진 십진수 개수 구하기

하나의 숫자 n이 주어졌다고 가정해 봅시다. 이진 십진수(binary decimal)란 양의 정수이면서 십진법 표기상 모든 자릿수가 0 또는 1로만 이루어진 수를 의미합니다. 예를 들어, 1001(천일)은 이진 십진수이지만, 1021은 그렇지 않습니다.

우리의 목표는 주어진 수 n을 여러 개의(서로 같아도 무방한) 이진 십진수의 합으로 표현하는 것입니다. 그리고 그때 필요한 이진 십진수의 최소 개수를 계산해야 합니다.

예를 들어 입력이 n = 121이라면 출력은 2가 됩니다. 왜냐하면 121은 110 + 11 또는 111 + 10처럼 두 개의 이진 십진수로 표현할 수 있기 때문입니다.

접근 방법

이 문제의 핵심 아이디어는 매우 간단합니다. 각 이진 십진수는 어떤 자릿수에도 최대 1만큼만 기여할 수 있습니다. 따라서 n의 자릿수 중 가장 큰 값(max digit)만큼의 이진 십진수가 반드시 필요하며, 동시에 그 개수면 충분합니다. 즉, 정답은 n의 최대 자릿수와 같습니다.

다음 단계를 따라 해결할 수 있습니다.

ans := -1
n > 0인 동안 반복:
    ans := ans와 (n mod 10) 중 최댓값
    n := n / 10
ans 반환

예제 코드

아래의 C++ 구현을 통해 더 잘 이해해 보겠습니다.

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

int solve(int n) {
    int ans = -1;
    while (n > 0) {
        ans = max(ans, n % 10);
        n /= 10;
    }
    return ans;
}
int main() {
    int n = 121;
    cout << solve(n) << endl;
}

입력

121

출력

2

동작 원리 설명

n = 121의 경우 각 자릿수는 1, 2, 1입니다. 이 중 가장 큰 자릿수는 2이므로, 최소 2개의 이진 십진수가 필요합니다. 실제로 110 + 11 = 121처럼 두 개의 이진 십진수만으로 n을 표현할 수 있음을 확인할 수 있습니다. 이 알고리즘은 자릿수만 검사하므로 시간 복잡도는 O(d)이며, d는 n의 자릿수입니다.