(BOJ) 7453 합이 0인 네 정수

문제 : https://www.acmicpc.net/problem/7453

* 혼자서 못 품 ㅠㅅㅠ

  다른 사람 블로그 보고 이해했다.

문제 풀이:

- n이 최대 4000이므로 단순하게 포문을 이용해 다 계산하면 시간 초과가 난다

- a, b, c, d를 한번에 계산해서 합이 0인지 판단하는 것이 아니라

  가능한 (a, b), (c, d)쌍의 값을 각각 모두 더하고 각 쌍의 합이 0인 것들의 개수가 답이 된다.

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

v.push_back(arr[i][2] + arr[j][3]);    // (c,d)의 합 모두 구하기

}

}

  * 처음에는 

    o .                              . o

    . o  꼴로만 구할 수 있고  o .  이런꼴은 못 구하는거 아닌가라는 생각을 함 ㅎㅎ

  

    but! i가 j 보다 작거나 같아 질 수 있으므로 모든 경우 다 구할 수 있음

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

ll t= arr[i][0] + arr[j][1];   // (a,b)의 합

ll a = lower_bound(v.begin(), v.end(), -t)-v.begin();   

ll b = upper_bound(v.begin(), v.end(), -t) - v.begin();

if(t+v[a]==0) cnt += b - a;

}

}

 * t가 아닌 -t 하는 이유: 

   (a+b)와 (c+d)의 합이 0이 되려면 서로 부호가 반대이여야한다.

   (a+b)=7일 때 대응하는 (c+d)를 찾으려면 -7을 찾아야 하므로

* -v.begin(); 하는 이유:

   lower_bound가 iterator를 리턴하므로 첫 위치의 iterator인 [v.begin()]를 빼주면 해당 위치를 구할 수 있다.

* cnt+=b-a; 인 이유:

  배열이 5 5 5 6 6 6 7 7 일 때

  b-a하면 6의 개수 바로 구할 수 있으니까 

 

필요한 알고리즘:

- upper_bound(), lower_bound();

ex)

int main ()

{

    int gfg[] = {5,6,7,7,6,5,5,6};

      

    vector<int> v(gfg,gfg+8);    // 5 6 7 7 6 5 5 6

  

    sort (v.begin(), v.end());  // 5 5 5 6 6 6 7 7

  

    vector<int>::iterator lower,upper;

    lower = lower_bound (v.begin(), v.end(), 6); 

    upper = upper_bound (v.begin(), v.end(), 6); 

  

    cout << "lower_bound for 6 at position " << (lower- v.begin()) << '\n';

    cout << "upper_bound for 6 at position " << (upper - v.begin()) << '\n';

  

    return 0;

}

output:

lower_bound for 6 at position 3
upper_bound for 6 at position 6