정수 n이 주어졌을 때, 오직 0과 1로만 이루어진 수들을 찾아 그 합이 정확히 n이 되도록 출력하는 것이 이번 문제의 목표입니다.
0과 1로만 구성된 대표적인 수로는 1, 10, 11이 있습니다. 이러한 수들은 각 자릿수가 0 또는 1뿐이므로, 이들을 적절히 더하면 어떤 양의 정수든 표현할 수 있습니다. 예를 들어 n = 31을 입력하면 10 + 10 + 11 또는 10 + 10 + 10 + 1처럼 여러 가지 조합이 가능합니다.
예시
입력: 31 출력: 10 10 10 1
접근 방법 및 알고리즘
이 문제는 그리디(greedy) 기법으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 남은 값이 20보다 크면 10을 우선 사용합니다. 10을 차감한 뒤 "10"을 출력합니다.
- 남은 값이 정확히 11이면 11을 사용합니다. 11을 차감한 뒤 "11"을 출력합니다.
- 그 외의 경우에는 1을 사용합니다. "1"을 출력하고 남은 값을 1 줄입니다.
구체적인 절차를 정리하면 다음과 같습니다.
- 변수 a에 n을 저장합니다.
- a가 0보다 큰 동안 다음을 반복합니다.
- a ÷ 10 > 0이고 a > 20이면 → a에서 10을 빼고 "10"을 출력
- a − 11 == 0이면 → a에서 11을 빼고 "11"을 출력
- 그 외 → "1"을 출력하고 a를 1 감소
- 반복이 종료되면 지금까지 출력된 수들의 합은 정확히 n이 됩니다.
1이라는 수가 항상 존재하기 때문에 어떤 양의 정수 n에 대해서도 이 방법은 반드시 답을 찾을 수 있다는 점이 이 알고리즘의 장점입니다.
C 언어 구현 예제
#include <stdio.h>
// 합이 n이 되는 0과 1로만 이루어진 수들을 출력하는 함수
void findNumbers(int n){
int a = n;
while(a > 0){
// 남은 값이 20보다 크면 10을 사용
if(a / 10 > 0 && a > 20){
a = a - 10;
printf("10 ");
}
// 남은 값이 정확히 11이면 11을 사용
else if(a - 11 == 0){
a = a - 11;
printf("11 ");
}
// 그 외에는 1을 사용
else{
printf("1 ");
a--;
}
}
}
// 드라이버 코드
int main(){
int N = 35;
findNumbers(N);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
10 10 1 1 1 1 11
N = 35일 때의 동작 과정을 살펴보면 다음과 같습니다. 처음에 a가 20보다 크므로 10을 두 번 차감하며(35 → 25 → 15) "10"을 두 번 출력합니다. 이후 a가 15가 되면 1을 네 번 출력하여(15 → 14 → 13 → 12 → 11) a를 11로 만들고, 마지막으로 11을 한 번에 차감하며 "11"을 출력합니다. 실제로 10 + 10 + 1 + 1 + 1 + 1 + 11 = 35로 합이 n과 일치하는 것을 확인할 수 있습니다.
복잡도 분석
매 반복마다 a가 최소 1씩 감소하므로 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다.