[BOJ] 1253 좋다

문제 요약 및 풀이

1253번: 좋다

문제 조건은 심플하다.

1. 어떤 수가 다른 수 2개로 구성되면 이는 좋은 수 이다.
2. 좋은수 a가 있다면, 주어진 수 중 a를 모두 카운트해야 한다.

근데, 만약 그냥 단순하게 이중 반복문으로 처리한다면, WA를 신랄하게 맞을거다.

d = {} # 각각 요소가 몇개 있는지 저장된 해쉬

...

ans = 0
for i in range(n):
  for j in range(i+1, n):
    s = L[i] + L[j]
    ans += d[s]
    d[s] = 0

왜?

아래같은 케이스가 있다.

(이게 큰 도움이 되었다… 테케를 알려준 천사님)

예시 1

6
1 -1 1 -1 0 0

예시 정답 1

6

예시 2

2
0 0

예시 정답 2

0

예시 3

3
1 -1 0

예시 정답 3

1

풀이 코드

그래서 d, d2로 중복되게 해쉬를 만들었고(그냥 NGD로..)

두 개의 숫자를 가져와서 더한 결과가 두 대의 숫자에 포함되고, 이게 유일한 경우라면 넘기는 케이스를 추가했다.

n = int(input())
L = [*map(int,input().split())]
d = {}
d2 = {}
ans = 0

for i in L:
  try:
    d[i] += 1
    d2[i] += 1
  except:
    d[i] = 1
    d2[i] = 1

for i in range(n):
  for j in range(i+1, n):
    s = L[i] + L[j]

    try:
      if (s == L[i] and d2[L[i]] == 1) or (s == L[j] and d2[L[j]] == 1) or (s == L[i] == L[j] and d2[L[i]] == 2):
        continue

      ans += d[s]
      d[s] = 0
    except:
      continue

print(ans)