★ C - [백준 2295] 세 수의 합 (feat. 이분탐색)

---

[백준 2295번] 세 수의 합 - 이분 탐색과 해시셋을 활용한 최적화 풀이

이번 포스트에서는 백준 온라인 저지의 2295번 문제, 세 수의 합 문제를 해결하는 방법에 대해 알아보겠습니다.
이 문제는 두 수의 합을 이용한 탐색 최적화를 배우기에 적합한 문제입니다. 문제의 접근 방법, 해결 전략, 그리고 C 언어로 구현한 코드를 단계별로 설명합니다.

---

1. 문제 설명

자연수로 이루어진 집합 U가 주어집니다.
세 수 a, b, c를 선택하여 a + b + c = d를 만족하는 가장 큰 d를 찾아야 합니다.

---

4. Checkpoint

 

해당 문제는 설계를 하지 못해 모범답안을 확인하고 문제를 풀었습니다.

" a + b + c = d를 a + b = d - c 형태로 변형" 방법을 생각해내지 못해 풀지 못한 것인데, 정말 간단한 수학접 접근이 복잡해보이는 문제를 간단히 해결할 수 있다는 점에서, 항상 이런 유형의 문제에 힘을 못쓴다는 것을 또 한번 느꼈습니다.

 

핵심 아이디어

문제를 변형하여 두 수의 합을 미리 계산해 두고, 이를 통해 탐색을 효율적으로 수행합니다.

• 문제 변환:
  a + b + c = d를 a + b = d - c 형태로 변형합니다.
• 이로 인해 두 수의 합을 저장한 집합을 생성하고, 이 값이 목표 값에 해당하는지 빠르게 확인할 수 있습니다.

---

5. 구현 과정

1단계: 두 수의 합 집합 생성

모든 a+ba + b 값을 계산하여 새로운 배열 SS에 저장합니다.
이를 통해 세 번째 수와의 연산을 최적화할 수 있습니다.

---

2단계: 이분 탐색을 이용한 탐색

• 배열 SS를 정렬합니다.
• 가장 큰 수부터 탐색하면서 d−c가 S에 존재하는지 확인합니다.
• 이분 탐색을 활용하여 빠르게 확인함으로써 시간 복잡도를 줄일 수 있습니다.

---

6. C 언어로 구현한 코드

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int binary_search(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return 1;  // target이 배열에 존재함
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return 0;  // target이 배열에 존재하지 않음
}

int main() {
    int n;
    scanf("%d", &n);
    int U[n];
    int S[n * n];  // 두 수의 합을 저장할 배열
    int s_index = 0;

    // 입력 받기
    for (int i = 0; i < n; i++) {
        scanf("%d", &U[i]);
    }

    // 배열 정렬
    qsort(U, n, sizeof(int), compare);

    // 두 수의 합 집합 생성
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            S[s_index++] = U[i] + U[j];
        }
    }

    // 두 수의 합 배열 정렬
    qsort(S, s_index, sizeof(int), compare);

    // 가장 큰 값부터 탐색
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            int target = U[i] - U[j];
            if (binary_search(S, s_index, target)) {
                printf("%d\n", U[i]);  // 결과 출력
                return 0;
            }
        }
    }

    return 0;
}

---

5. 코드 설명

5-1. 입력 및 정렬

for (int i = 0; i < n; i++) {
    scanf("%d", &U[i]);
}

qsort(U, n, sizeof(int), compare);

• nn개의 자연수를 입력받고 배열 UU에 저장한 후, 오름차순으로 정렬합니다.

---

5-2. 두 수의 합 집합 생성

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        S[s_index++] = U[i] + U[j];
    }
}

• 이중 반복문을 통해 UU의 원소 중 두 수의 합을 모두 계산하여 배열 SS에 저장합니다.

---

5-3. 이분 탐색을 이용한 탐색

for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= i; j++) {
        int target = U[i] - U[j];
        if (binary_search(S, s_index, target)) {
            printf("%d\n", U[i]);
            return 0;
        }
    }
}

• 가장 큰 수부터 탐색하며, U[i] - U[j]가 배열 S에 존재하는지 이분 탐색을 통해 확인합니다.
• 존재한다면 해당 U[i]가 조건을 만족하는 가장 큰 값이므로 출력하고 프로그램을 종료합니다.

---

6. 시간 복잡도 분석

• 두 수의 합 계산: O(N^2)
• 정렬: O(N2log⁡N)
• 탐색: O(N2log⁡N)

따라서 총 시간 복잡도는 O(N2log⁡N)입니다.

---

7. 결과 출력 예시

입력 예시

5
1 2 3 4 5

출력 예시

5

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.