[백준] 1253번 - 좋다

문제 링크 : https://www.acmicpc.net/problem/11003

 

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

풀이

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

nums.sort()
count = 0

for n in range(N):
    k = nums[n]
    start = 0
    end = N-1
    while start < end:
        total = nums[start] + nums[end]
        if total == k:
            if start != n and end != n:
                count+=1
                break
            elif start == n:
                start+=1
            else:
                end-=1
        elif total < k:
            start+=1
        else:
            end-=1
print(count)

 

해설

• 리스트를 정렬한 뒤 투포인터로 구간합을 구하는 문제였다.
• 파이썬 문법이 가물가물해서 and를 &로 적었다가 오래 헤맨 문제 .. ㅎㅎ..
• start나 end가 n인지를 total == k일 때 판별해줘야하는 이유는 입력이 '0 1' 이런식으로 처음부터 바로 total == k 인 값들로 들어올 수도 있기 때문이다.