좋다(백준 1253)

문제

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

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

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

입력

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

출력

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

 

입출력

10
1 2 3 4 5 6 7 8 9 10

8

 

입출력

3,4,5,6,7,8,9,10은 좋다.

초기 코드 

N = int(input()) # 개수
L = list(map(int, input().split())) # 숫자 리스트
count = 0 # 좋은 수

L.sort() #정렬된 리스트

for k in range(N):
    i = 0
    j = k - 1
    while i < j:
        if (L[i] + L[j]) > L[k]:
            j -= 1
        elif (L[i] + L[j]) < L[k]:
            i += 1
        else: 
            count += 1
            break

print(count)

 

- 숫자 리스트를 입력받고 투 포인터 알고리즘으로 접근하였음

 

문제점

4
0 0 0 0

- 위 데이터를 입력으로 가져오는 경우, 모든 수가 '좋은 수'로 4라는 정답을 내놓아야 하지만 처음 k = 0 의 경우 while 루프가 실행되지 않아 count 되지 않음

 

최종 코드 

N = int(input()) # 개수
L = list(map(int, input().split())) # 숫자 리스트
count = 0 # 좋은 수

L.sort() #정렬된 리스트

for k in range(N):
    i = 0
    j = N - 1
    while i < j:
        if (L[i] + L[j]) > L[k]:
            j -= 1
            
        elif (L[i] + L[j]) < L[k]:
            i += 1
       
        else: 
            if i != k and j != k: # i, j 모두 k가 아닌경우  
                count += 1
                break # 맞는경우 루프 탈출
            elif i == k:
                i += 1
            elif j == k:
                j -= 1

print(count)