1253:좋다

02 Sep 2022 in PS on Ps

문제

코드

N=int(input())
arr=list(map(int,input().split()))
arr.sort()
cnt=0
for i in range(N):
    l,r=0,N-2
    tmp=arr[0:i]+arr[i+1:N]
    sum=tmp[l]+tmp[r]

    while l<r:
        sum=tmp[l]+tmp[r]
        if sum==arr[i]:
            cnt+=1
            break
        
        if sum<arr[i]:
            l+=1
        else:
            r-=1
print(cnt)

풀이

리스트를 정렬 후 가장 작은수와 가장 큰수를 2개의 기준으로 잡는다.
for문으로 리스트안에 있는 수를 선택하면서 두 개의 기준을 더한 값과 비교
비교 후 선택한 수가 작다면 작은 수를 키워본다 (vice versa)

후기

처음에는 어떻게 인덱스를 접근해서 합을 구할까 많이 생각했다.
정렬 후 양쪽에서 접근하면 sum의 결과를 효율적으로 접근 할 수 있다는 생각이 들었다.
greedy를 푸는 생각처럼 풀었다.