[1253] 좋다

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

1253 - 좋다

본문

$N$개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

$N$개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 $N$($1 \leq N \leq 2\,000$), 두 번째 줄에는 $i$번째 수를 나타내는 $A_i$가 $N$개 주어진다. ($\lvert A_i \rvert \leq 1\,000\,000\,000$, $A_i$는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

---

풀이

1차원적으로 생각하면 간단하다. 배열 안의 모든 원소에 대해 3중 loop를 통해 각각을 $a$, $b$, $c$로 놓고, $a+b=c$를 만족하는 $c$의 개수를 찾아내면 되는 문제다. 문제에서는 매칭되는 횟수가 아닌 좋은 수의 개수, 즉 $c$의 개수를 출력하라고 했으니, 중복체크를 피하기 위해 visit 배열을 만들어두는 것이 좋다.

다만 시간이 문제다. 세 수는 모두 달라야한다는 규칙이 있다고 해도, 3중 loop를 통해 계산하는 것은 $O(N^3)$이고, $N=2000$이므로 제한시간인 2초 이내에 돌 수 없다. 다른 방법을 써서 탐색 횟수를 줄이도록 하자.

이 문제를 풀면서 탐색 횟수를 줄이기 위해 내가 사용한 방법은 크게 2가지다.

• 배열 원소 압축
  • 같은 값을 가진 원소를 ‘하나의 배열 칸’으로 묶어내었다. 같은 값을 가지더라도 위치가 달랐으면 다른 수로 인식하므로, 배열은 원소가 나타내는 값과 그 원소가 존재했던 개수를 묶어 기록한다.
  • 함수 :: array_init()
• 이분 탐색
  • 어떤 수 $a$와 $b$를 정해놓고, $a+b=c$를 만족하는 $c$가 존재하는지 확인하는 방법으로 이분 탐색을 활용했다. 이분 탐색을 활용하면 $O(N^3)$이었던 기존의 복잡도를 $O(N^2 \log N)$으로 줄일 수 있게 된다.
  • 함수 :: binary_search()

위 2개의 방법을 사용하여 탐색 횟수를 줄였다. 사실 이분 탐색을 유효하게 하기 위해 원소 압축을 진행했다고 볼 수 있어서, 탐색 횟수를 줄이는 방법으로는 이분 탐색을 활용했다고 얘기할 수 있다.

몇가지 유의할 점으로, 배열 압축을 통해 같은 원소들은 한 칸에 몰아넣었지만, 제각기 다른 수임을 기억해야한다. 또 ‘좋은 수’는 꼭 다른 2개의 수의 합으로 이루어져야하며, 하나의 좋은 수 $c$가 다른 여러 조합의 합으로 나타낼 수 있다고 하더라도 좋은 수의 개수를 세야하므로 횟수는 1번만 추가해야한다.

• 참고 알고리즘 : 이분 탐색

코드

사용 언어 : C

최종 수정일 : 2024 / 4 / 23

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

typedef struct Node {
    int v;
    int cnt;
} ND;

#define MAX_IDX 2000
const int NONE = -1;

bool good[MAX_IDX + 1];
ND arr[MAX_IDX];
int n;

#define max(a, b) (((a) > (b)) ? (a) : (b))
int cmp(ND* a, ND* b) { return a->v > b->v; }

int binary_search(int left, int right, int value) {
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].v == value) {
            return mid;
        } else if (arr[mid].v < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return NONE;
}

void array_init() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int temp;
        scanf("%d", &temp);
        arr[i] = (ND){temp, 1};
    }
    qsort(arr, n, sizeof(ND), cmp);

    int overlapped = 0;
    for (int i = 1; i < n; ++i) {
        if (arr[i].v == arr[i - overlapped - 1].v) {
            arr[i - overlapped - 1].cnt += 1;
            ++overlapped;
        } else {
            arr[i - overlapped] = (ND){arr[i].v, 1};
        }
    }
    n -= overlapped;
    return;
}

int main() {
    array_init();
    int result = 0;

    for (int a = 0; a < n; ++a) {
        /* 좋은 수가 같은 값을 가진 숫자 2개의 합인 경우 */
        if (arr[a].cnt >= 2) {
            int c = binary_search(0, n, arr[a].v + arr[a].v);

            if (c != NONE && good[c] == false) {
                if ((a == c && arr[a].cnt == 2) == false) {
                    good[c] = true;
                    result += arr[c].cnt;
                }
            }
        }

        /* 좋은 수가 다른 값을 가진 숫자 2개의 합인 경우 */
        for (int b = a + 1; b < n; ++b) {
            int c = binary_search(0, n, arr[a].v + arr[b].v);

            if (c != NONE && good[c] == false) {
                if ((a == c && arr[c].cnt == 1) == false &&
                    (b == c && arr[c].cnt == 1) == false) {
                    good[c] = true;
                    result += arr[c].cnt;
                }
            }
        }
    }

    printf("%d", result);
    return 0;
}

• good[] : 좋은 수였는지 확인하기 위한 visit 배열