C++로 숫자 n을 표현하는 최소 개수의 서로 다른 자릿수 찾기

문제 이해

숫자 n이 주어졌다고 가정해 봅시다. 우리는 이 숫자를 합이 n이 되도록 하나 이상의 0이 아닌 자릿수(1~9)로 분할하려고 합니다. 이때 목표는 사용되는 서로 다른 자릿수의 종류가 최소가 되는 해를 찾는 것입니다.

예를 들어 입력이 n = 13이라면, 출력은 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]이 됩니다.

접근 방법

이 문제의 핵심은 자릿수의 '개수'가 아니라 '종류'를 최소화하는 데 있습니다. 숫자 1만 반복해서 사용하면 어떤 n에 대해서도 서로 다른 자릿수의 종류는 단 한 가지(1)뿐이며, 이것보다 적을 수는 없습니다. 따라서 정답은 항상 숫자 1을 n번 출력하는 것입니다.

해결 절차는 다음과 같습니다:

i := 0으로 초기화하고, i < n인 동안 반복(i는 1씩 증가):
    1을 출력

예제 구현

아래 C++ 구현 예시를 통해 더 잘 이해해 보겠습니다:

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    for (int i = 0; i < n; i++)
    printf("1, ");
}
int main(){
    int n = 13;
    solve(n);
}

입력

13

출력

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

복잡도 분석

시간 복잡도는 O(n)이며, 추가 메모리 사용량은 O(1)입니다. n이 커질수록 출력 길이가 선형적으로 늘어나지만, 알고리즘 자체는 매우 단순하고 효율적입니다.