[백준] 3151번 합이 0

basic-algo-lecture/workbook/0x13.md at master · encrypted-def/basic-algo-lecture

바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.

github.com

처음 코드(메모리 초과..)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int binarySearchMin(int target, vector<pair<int, int>>& table) {
    int st = 0;
    int en = table.size() - 1;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (table[mid].first < target) {
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }
    return st;
}

int binarySearchMax(int target, vector<pair<int, int>>& table) {
    int st = 0;
    int en = table.size() - 1;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (table[mid].first <= target) {
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }
    return st;
}

int operate(pair<pair<int, int>, pair<int, int>> target, vector<pair<int, int>>& table) {
    int targetLevel = target.first.first + target.second.first;

    // binarySearch 로 target 의 minIdx, maxIdx 를 찾아야행
    int minIdx = binarySearchMin(-targetLevel, table);
    int maxIdx = binarySearchMax(-targetLevel, table);

    int cnt = 0;
    for (int i = minIdx; i < maxIdx; i++) {
        if (table[i].second == target.first.second || table[i].second == target.second.second) continue;

        cnt++;
    }

    return cnt;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<pair<int, int>> levels(n);
    for (int i = 0; i < n; i++) {
        int level;
        cin >> level;
        // 나중에 levels 을 level 을 기준으로 오름차순 정렬했을 때 이전 인덱스 잃어버리지 않도록..
        levels[i] = { level, i }; // 레벨이랑 인덱스 같이 저장해
    }

    // 일단 levels 의 요소를 두개씩 짝지어서 새로운 배열 하나 만들어야함
    // pair<int, int> 형으로 데이터 저장하면 될 것 같은드ㅔ
    vector<pair<pair<int, int>, pair<int, int>>> twoLevels;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            twoLevels.push_back({ {levels[i]}, {levels[j]} });
        }
    }
    sort(levels.begin(), levels.end()); // 일단 level 을 기준으로 오름차순 정렬

    long long answer = 0; // 팀의 수
    // 일단 twoLevels 돌면서 levels 에 자기랑 더했을 때 0이 되는 애가 있는지 찾아야함.
    for (int i = 0; i < twoLevels.size(); i++) {
        answer += operate(twoLevels[i], levels);
    }
    cout << answer / 3;

    return 0;
}

솔직히 잘풀었다고 생각했는데 채점하다가 메모리초과 떠서 슬펐다. 쓸데없이 인덱스 같은 거 저장해서 twoLevels 같은거 안 만들고 푸는 방법을 고안해야했다..

그리고 내 코드는 (a,b,c), (b, c, a), (c, a, b) 처럼 똑같은 수로 이루어진 경우까지 그냥 센 다음에 나중에 3으로 나눠주도록 했는데 이것도 꽤나 비효율적인듯.. 이것도 아예 초장부터 똑같은 수로 이루어진 경우를 안 셀 수 있도록 해야했다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

using namespace std;

int binarySearchMin(int target, int st_, int en_, vector<int>& levels) {
    int st = st_;
    int en = en_;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (levels[mid] < target) {
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }
    return st;
}

int binarySearchMax(int target, int st_, int en_, vector<int>& levels) {
    int st = st_;
    int en = en_;

    while (st <= en) {
        int mid = (st + en) / 2;

        if (levels[mid] <= target) {
            st = mid + 1;
        }
        else {
            en = mid - 1;
        }
    }
    return st;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> levels(n);
    for (int i = 0; i < n; i++)
        cin >> levels[i];
    sort(levels.begin(), levels.end()); // 오름차순으로 정렬하고 시작

    long long answer = 0;
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            int target = levels[i] + levels[j];

            // -target 이 들어갈 수 있는 가장 작은 인덱스와 가장 큰 인덱스를 구해
            int minIdx = binarySearchMin(-target, j+1, n - 1, levels);
            int maxIdx = binarySearchMax(-target, j+1, n - 1, levels);

            answer += (maxIdx - minIdx);
        }
    }
    cout << answer << "\n";

    return 0;
}

일단 (a, b, c), (b, a, c), (c, a, b) 와 같은 중복되는 것을 막기 위해서 미리 levels 를 오름차순으로 정렬하고 시작한다.

이중포문에서 i 와 j 의 범위와, binarySearch 할 때 st 의 인덱스로 j+1 값을 넣는 모습을 보면 저절로 중복되는 경우가 안 생기도록 할 수 있다.

이거 백트래킹할 때 썼던건데 그새 까먹고 그냥 중구난방으로 풀었다는 사실이;; 뭐 이번에 다시 알게됐으니까 최대한 기억해보자..

이제 -target 값이 들어갈 수 있는 minIdx 와 maxIdx 값을 찾아서 answer 에 (maxIdx - minIdx) 값을 더해주면 된다. 아, 그리고 answer 의 범위를 int 로 설정하면 오버플로우 나는 경우가 있어서 틀린다. 나는 long long 으로 설정해줘서 겨우 통과했다. -_-;;

티스토리툴바