[백준]1253 좋다

1. 풀이

(1) L의 길이는 최대 2000. 두개씩 모든경우를 합쳐야 하므로 2000C2번의 반복이 필요하다.

(2) sort된 L리스트에서 중복된 좋은수의 가장 앞부분을 찾아서 isGoodNumL에 표시한다.

- L리스트에 모든 숫자가 서로 다르다면 그냥 이분탐색을 하면 되지만, 같은 숫자가 있을수도 있기 때문에 lower bound를 찾아주고(가장 앞에있는 위치), 다음단계에서 중복된 "좋은수"를 찾아준다.

- 처음엔 upperbound와 lowerbound를 모두 찾은 뒤 lowerbound에서 upperbound까지 모두 isGOodNumL에 1로 표시해 주려고 했지만, 만약 최악의경우 upperbound-lowerbound가 2000이 되면 시간초과가 발생할 수 있기 때문에 조합 반복문을 벗어난 뒤 한꺼번에 처리((3)과 같이)했다.

(3) 중복된 좋은수를 모두 찾아준다.

# 중복된 좋은수 모두 찾기
goodNumL=[]
for i in range(N):
    if isGoodNumL[i]==1:
        goodNumL.append(L[i])
    else:
        if L[i] in goodNumL:
            isGoodNumL[i]=1

*시간복잡도

모든 2개 숫자의 합을 조합으로 확인해야 하므로 2000C2 반복.

한번의 반복당 lowerbound를 찾는데 log2000.

따라서 2000C2 * log2000

 

2. 소스코드

from itertools import combinations
N=int(input())
L=list(map(int,input().split()))
L.sort()
comb=list(combinations([i for i in range(N)],2))

def lowerBound(target):
    left=0
    right=N
    while(left<right):
        mid=(left+right)//2
        if target<=L[mid]:
            right=mid
        else:
            left=mid+1
    return right

# 좋은수중 가장 빠른 index에 1이 들어가있는 isGoodNumL 리스트
isGoodNumL=[0 for i in range(N)]
for a,b in comb:
    num=L[a]+L[b]
    if num>L[N-1]:
        continue
    numIndx=lowerBound(num)
    if numIndx!=a and numIndx!=b and L[numIndx]==num:
        isGoodNumL[numIndx]=1

# 중복된 좋은수 모두 찾기
goodNumL=[]
for i in range(N):
    if isGoodNumL[i]==1:
        goodNumL.append(L[i])
    else:
        if L[i] in goodNumL:
            isGoodNumL[i]=1


print(sum(isGoodNumL))