문제 요약 및 풀이
1253번: 좋다
문제 조건은 심플하다.
- 어떤 수가 다른 수 2개로 구성되면 이는 좋은 수 이다.
- 좋은수 a가 있다면, 주어진 수 중 a를 모두 카운트해야 한다.
근데, 만약 그냥 단순하게 이중 반복문으로 처리한다면, WA를 신랄하게 맞을거다.
1
2
3
4
5
6
7
8
9
10
11
| 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
예시 정답 1
예시 2
예시 정답 2
예시 3
예시 정답 3
풀이 코드
그래서 d, d2로 중복되게 해쉬를 만들었고(그냥 NGD로..)
두 개의 숫자를 가져와서 더한 결과가 두 대의 숫자에 포함되고, 이게 유일한 경우라면 넘기는 케이스를 추가했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| 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)
|
