[파이썬] 백준 3151 : 합이 0 (골드4)

[파이썬] 백준 3151 : 합이 0 (골드4)

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

---

풀이

방향성 생각

• 입력 크기가 10000이라, dict으로 val:개수 형태로 반환해서 계산하기
• $O(N)$으로 압축해주고, aaa, aab 에서 각 $O(N)$이라 $O(2N)$이다.
• abc로 0을 만드는 경우가 $O(N^2)$이라 브루트포스로 풀이

 

---

전체코드

from collections import defaultdict as dd

N = int(input())
arr = list(map(int,input().split()))

answer = [0,0,0]
cnts = dd(int)
for a in arr:
    cnts[a] += 1

# a a a
if cnts[0] >= 3:
    answer[0] += cnts[0]*(cnts[0]-1)*(cnts[0]-2)

# a a b 
for a in cnts.keys():
    if a and cnts[a]>=2 and -2*a in cnts:
        answer[1] += (cnts[a]*(cnts[a]-1))*cnts[-2*a]

# a b c 
for a in cnts.keys():
    for b in cnts.keys():
        c = -(a+b)
        if c in cnts and a!=b and a!=c and b!=c:
            answer[2] += cnts[a]*cnts[b]*cnts[c]

print(answer[0]//6 + answer[1]//2 + answer[2]//6)

코멘트

• 압축 효과가 별로 없는 케이스도 많고, dict을 사용해서 python3는 터졌고 pypy3로 풀이.