[백준/C++] 알고리즘 3151번 - 합이 0

 

안녕하세요. 테크지니어22입니다.

 

오늘은 백준 알고리즘 2467번 - 합이 0 문제를 풀어보도록 하겠습니다.

 

https://www.acmicpc.net/problem/3151

3151번: 합이 0

 

[문제 접근]

시간제한이 4초로 넉넉하고

N의 최대값이 10,000이기 때문에 O(N^2)은 가능하고 O(N^3)은 불가능합니다.

O(N^2logN)풀이가 가능한 이분 탐색을 떠올렸습니다.

 

[풀이 전략]

1. 이중 for문 사용합니다.

2. lower_bound와 upper_bound를 사용하여 중복개수도 셉니다

 

[코드]

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

// 합이 0

int n ; // 학생의 수
int arr[10'001]; // 학생 코딩실력 저장 배열
long long num  ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin>> n ;

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

    sort(arr,arr+n);
    
    for(int i = 0 ; i < n-1; i++)
      for(int j = i+1 ; j < n ; j++) {
        auto lower = 
        lower_bound(arr+j+1,arr+n,-arr[i]-arr[j]);

        auto upper =
        upper_bound(arr+j+1,arr+n,-arr[i]-arr[j]);

        num += (upper - lower) ; 
      }

    cout << num ; 
}

 

[배울 점]

- 이분 탐색문제를 풀때 for문을 사용할 경우 이전에 방문한 곳을 다시 방문할 필요가 있는지 생각해보기. 

- 출력값의 크기를 고려하여 int형을 사용할 지 long long형을 사용할 지 생각하기.