백준 9440번 [숫자 더하기](C++) -yes6686- 티스토리

백준 문제 풀이: 9440 (숫자 더하기)

---

문제 링크: https://www.acmicpc.net/problem/9440

문제 설명:

주어진 숫자들을 두 개의 정수로 나누어 합이 최소가 되도록 만듭니다. 각 숫자는 반드시 사용되어야 하며, 두 정수의 앞자리에 0이 올 수 없습니다. 입력은 여러 개의 테스트 케이스로 구성되며, 첫 번째 입력 값이 0이면 프로그램이 종료됩니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int arr[15]; // 숫자 저장 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    while (true) {
        int n; // 숫자의 개수
        cin >> n;
        if (n == 0) break; // 0이면 종료

        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        // 숫자를 오름차순으로 정렬
        sort(arr, arr + n);

        // 두 개의 정수 생성
        string num1 = "", num2 = "";
        for (int i = 0; i < n; i++) {
            if (num1.empty()) {
                num1 += to_string(arr[i]);
            } else if (num2.empty()) {
                num2 += to_string(arr[i]);
            } else if (num1.length() <= num2.length()) {
                num1 += to_string(arr[i]);
            } else {
                num2 += to_string(arr[i]);
            }
        }

        // 두 수를 정수로 변환 후 합산
        int a = stoi(num1);
        int b = stoi(num2);
        cout << a + b << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 주어진 숫자들을 정렬하여 최소값이 앞에 오도록 두 개의 정수를 생성합니다.
• 구현 세부사항:
  • sort(arr, arr + n): 주어진 숫자를 정렬하여 작은 숫자부터 사용하도록 합니다.
  • 두 정수를 번갈아 가며 숫자를 배정하여 두 수의 길이가 균형을 이루도록 합니다.
  • stoi(): 문자열을 정수로 변환하여 합산합니다.
• 시간 복잡도 분석:
  • 정렬 단계: O(n log n)
  • 숫자 배정 단계: O(n)
  • 전체 시간 복잡도는 O(n log n)입니다.

---

결과

주어진 숫자 리스트에 대해 두 정수의 합이 최소가 되는 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!