[BOJ] 3273 두수의 합

date

Jul 17, 2023

slug

boj-3273

author

status

Public

문제 링크

https://www.acmicpc.net/problem/3273

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

문제풀이

먼저 배열의 크기 n을 입력받고

n개에 해당하는 배열을 입력받은 후에

순서쌍 (ai,aj)의 합을 만족하는 x를 입력받는다.

배열을 정렬한후

스타트 포인터는 배열의 첫번째

엔드포인터는 배열의 마지막

스타트 포인터와 엔드포인터 순서쌍의 합이 x보다 크다면

엔드포인터의 인덱스를 하나 내려준다.

why? x보다 작아질 가능성이 있기때문

순서쌍의 합이 x보다 작으면

스타트 포인터의 인덱스를 하나 올려준다.

why? x보다 커질 가능 성이 있기 떄문

만약 x와 같다면

카운트를 1증가하고, 스타트를 1증가, 엔드를 1감소

why? 배열에 들어있는 원소값은 서로 다르기 떄문ㅇ

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int, input().split()))
x = int(input())

li.sort()
first_pointer = 0
end_pointer = len(li)-1
count = 0
while True:
    if first_pointer >= end_pointer:
        break
    result = li[first_pointer] + li[end_pointer]
    if result > x:
        end_pointer-=1
    elif result < x:
        first_pointer+=1
    else:
        count+=1
        first_pointer+=1
        end_pointer-=1
        
print(count)

시간복잡도

O(1)

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력


9
5 12 7 10 9 1 2 3 11
13

예제 출력

알고리즘 분류

정렬

두 포인터