1. 문제설명

문제 설명이 길어서 핵심만 언급하겠다.
N개의 수열에서 세 개의 수 합이 0이 되는 경우의 수를 구하는 문제이다.

2. 알고리즘 설계

문제가 매우 투포인터스럽다.
lower_bound, upper_bound를 통해 문제를 해결할 수 있었다.
- 같은 값의 개수 = upper_bound() - lower_bound()
- #include <xutility> 안에 있다.
- 자세한 설명
- 사용법
  - lower_bound(arr, arr+n, target) - arr
  - 1번째, 2번째 인자는 탐색 범위이다.
  - index를 얻기 위해서 배열의 이름(== 주소값)을 빼주어야 한다.

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, A[10005];
long long ans;

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

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> A[i];
    
    sort(A, A+n);

    for(int i=0; i<n-2; i++) {
        for(int j=i+1; j<n-1; j++) {
            int cmp = A[i] + A[j];
            int l = lower_bound(A + j + 1, A + n, -cmp) - A;
            int u = upper_bound(A + j + 1, A + n, -cmp) - A;
            ans += u-l;
        }   
    }

    cout << ans;

    return 0;
}

4. 소감

해당 개념은 과거에 접해본 적이 있어서, github issue page에 정리해두었다.
그 당시 문제를 풀 때 블로그를 참고해서 풀어서, 같은 유형인데 풀이법이 바로 떠오르지 않았다.
백준을 풀다보면, 맞았습니다!!를 보게되면 다시 안 보게 되는 경향이 있는 거 같다.
- 블로그 풀이는 최대한 늦게 참고하되, 코드는 절대 베끼지 말자..!

BOJ 3151. 합이 0

1. 문제설명

2. 알고리즘 설계

3. 전체 코드

4. 소감