문제 📚
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.
[입력]
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
[출력]
좋은 수의 개수를 첫 번째 줄에 출력한다.
input #1
10
1 2 3 4 5 6 7 8 9 10
output #1
8
input #2
6
0 0 3 3 3 3
output #2
4
문제 설명 👩🏫
문제 설명이라 적고 입력 예제 설명이라 쓴다
두 개의 수의 합으로 나타낼 수 있는 수 = 좋은 수
input #1의 경우 주어진 숫자들 중에서,
1 2 3 4 5 6 7 8 9 10
1과 다른 수를 더했을 때 나올 수 있는 수 : 3,4,5,6,7,8,9,10
2와 다른 수를 더했을 때 나올 수 있는 수 : 3,5,6,7,8,9,10
3과 다른 수를 더했을 때 나올 수 있는 수 : 4,5,7,8,9,10
4와 다른 수를 더했을 때 나올 수 있는 수 : 5,6,7,9,10
5와 다른 수를 더했을 때 나올 수 있는 수 : 6,7,8,9
6과 다른 수를 더했을 때 나올 수 있는 수 : 7,8,9,10
7과 다른 수를 더했을 때 나올 수 있는 수 : 8,9,10
8과 다른 수를 더했을 때 나올 수 있는 수 : 9,10
9와 다른 수를 더했을 때 나올 수 있는 수 : 10
좋은 수는 3,4,5,6,7,8,9,10으로 총 8개
기본 예제인 input #1만 보고 완전 탐색 풀이법을 시도했다. 두 수를 더해서 나올 수 있는 모든 경우를 구한 후, set 자료형을 이용해 중복을 배제하여 좋은 수를 카운트 했는데 낮은 정답률에 이유가 있듯 보기 좋게 틀렸다. 처음에는 이유를 몰라 헤맸었는데 input #2를 보고 어떻게 풀어야 하는지 감이 왔다. 더한 두 수를 제외했을 때, 좋은 수의 존재 여부를 고려해야 했었다.
input #2 의 경우 주어진 숫자들 중에서,
0 0 3 3 3 3
0+0=0인데 만족하는 좋은 수가 존재하지 않는다.
0+3=3으로 각각 4개의 경우의 수가 존재한다.
그러므로 출력값은 4가 된다.
코드 👩💻
# 좋은 수의 개수를 세는 함수
def solve():
cnt = 0
nums.sort()
for i in range(len(nums)):
if search(i, nums[i]):
cnt += 1
print(cnt)
# 좋은 수가 들어있는지 탐색하는 함수
def search(i, target):
temp = nums[:i] + nums[i+1:] # 타겟이 되는 nums[i]를 제외하고 탐색
# print(temp)
left = 0
right = n-2 # 마지막 인덱스 n-1에서 타겟값 하나 더 빼서 n-2
while left < right:
sum = temp[left] + temp[right]
if target < sum:
right -= 1
elif target > sum:
left += 1
else:
# print(i,target)
return True
return False
import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
solve()
target 값을 정하고 nums[i] (= target) 값을 제외한 배열에서 left, right 투 포인터를 이용한 탐색을 진행한다. 이런 식으로 풀이하면 input #2에서 두 수의 합이 배열 내에 존재하지 않을 경우를 고려하여 문제를 해결할 수 있다.
