141. 합이 0인 네 정수

아현·2021년 7월 7일
0

Algorithm

목록 보기
142/400

백준




1. Python



from collections import defaultdict 
import sys 

input = sys.stdin.readline 

n = int(input()) 
alist, blist, clist, dlist = [], [], [], [] 

for _ in range(n): 
  a, b, c, d = map(int, input().split()) 
  alist.append(a); blist.append(b); clist.append(c); dlist.append(d) 
  
abdic = defaultdict(int) 
for i in range(n): 
  for j in range(n): 
    ab = alist[i] + blist[j] 
    abdic[ab] += 1 
    
result = 0 
for i in range(n): 
  for j in range(n):
    cd = -(clist[i] + dlist[j]) 
    if cd in abdic: 
      result += abdic[cd] 

print(result)






2. C++



#include <cstdio>
#include <vector>
#include <algorithm> 
using namespace std;
typedef long long LL;

int n;
vector<int> a, b, c, d;
vector<int> ab, cd;

/*
LL st1() {
    // 전략 1. 정렬 없이 바로 map 사용
}

LL st2_1() {
    // 전략 2. 정렬 ==>
    // 전략 2-1. lower_bound, upper_bound 
    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());
}
*/

LL st2_2() {
    LL res = 0, cnt = 0;
    // 전략 2. 정렬 ==>
    // 전략 2-2. 안쓰고 ==> 
    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());
    int p_cd = cd.size() - 1;
    for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
        int target = -ab[p_ab];
        if (0 < p_ab && ab[p_ab] == ab[p_ab - 1]) {
            res += cnt;
        }
        else {
            while (0 <= p_cd && target < cd[p_cd]) {
                p_cd--;
            }
            cnt = 0;
            while (0 <= p_cd && target == cd[p_cd]) {
                cnt++;
                p_cd--;
            }
            res += cnt;
        }
    }
    return res;
}

/*
LL st2_2() {
    LL res = 0, cnt = 0;
    // 전략 2. 정렬 ==>
    // 전략 2-2. 안쓰고 ==> 
    sort(ab.begin(), ab.end());
    sort(cd.begin(), cd.end());
    int p_cd = cd.size() - 1;
    for (int p_ab = 0 ; p_ab < ab.size() ; p_ab++) {
        if (0 < p_ab && ab[p_ab - 1] == ab[p_ab]) {
            res += cnt;
        }
        else {
            cnt = 0;
            while (0 <= p_cd && -ab[p_ab] < cd[p_cd]) p_cd--;
            while (0 <= p_cd && -ab[p_ab] == cd[p_cd]) cnt++, p_cd--;
            res += cnt; 
        }
    }
    return res;
}
*/

int main() {
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++) {
        int u, v, w, x;
        scanf("%d%d%d%d", &u, &v, &w, &x);
        a.push_back(u);
        b.push_back(v);
        c.push_back(w);
        d.push_back(x);
    }
    // a,b 로 만들수 있는 합의 조합 ==> ab
    // c,d로 만들수 있는 합의 조합 ==> cd
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++) {
            ab.push_back(a[i] + b[j]);
            cd.push_back(c[i] + d[j]);
        }
    }

    //printf("%lld", st_1());
    //printf("%lld", st_2_1());
    printf("%lld", st2_2());
}

profile
For the sake of someone who studies computer science

0개의 댓글