문제 설명
0부터 9 사이의 숫자로만 구성된 배열이 주어집니다. 이때 배열의 숫자들을 활용하여 만들 수 있는 두 수의 합 중에서 가장 작은 값을 찾는 것이 목표입니다. 단, 배열에 포함된 모든 숫자를 반드시 한 번씩 사용해야 한다는 점에 유의해야 합니다.
예시
입력 배열이 {7, 5, 1, 3, 2, 4}라고 가정해 보겠습니다. 이 경우 숫자들을 조합하여 135와 247이라는 두 수를 만들 수 있으며, 두 수의 합은 382입니다. 어떻게 조합하더라도 이보다 작은 합을 만들 수 없으므로, 최소 합은 382가 됩니다.
알고리즘
최소 합을 얻기 위한 핵심 아이디어는 작은 숫자일수록 높은 자릿수(10의 거듭제곱 자리)에 배치하는 것입니다. 이 원칙에 따른 접근 방식은 다음과 같습니다.
- 배열을 오름차순으로 정렬합니다.
- 정렬된 배열에서 인덱스를 번갈아 가며(짝수 인덱스와 홀수 인덱스) 숫자를 하나씩 선택하여 두 개의 수를 만듭니다.
이렇게 하면 두 수의 자릿수가 균형 있게 나뉘고, 동시에 가장 작은 숫자들이 가장 높은 자릿수에 위치하게 되어 전체 합이 자연스럽게 최소화됩니다. 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMinSum(int *arr, int n) {
sort(arr, arr + n);
int a = 0;
int b = 0;
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
a = a * 10 + arr[i];
} else {
b = b * 10 + arr[i];
}
}
return a + b;
}
int main() {
int arr[] = {7, 5, 1, 3, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum sum = " << getMinSum(arr, n) << endl;
return 0;
}
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
Minimum sum = 382