문제:
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력:
문제의 조건을 만족하는 쌍의 개수를 출력한다.
풀이방법:
앞에서부터 시작하는 포인터와 뒤에서부터 시작하는 포인터 두 개를 사용해서 합이 x가 되는 점들을 찾는다. 탐색이 종료되는 조건은 포인터가 교차하는 순간이며, 탐색하기 전에 정렬을 하도록 한다.
포인터의 이동은 다음과 같은 조건에 따른다.
1. 두 포인터의 값이 x와 같다면, 양 포인터를 모두 이동시킨다.
2. x보다 작다면 앞 포인터를 움직여 값을 키운다.
3. x보다 크다면 뒷 포인터를 움직여 값을 낮춘다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
n = int(input())
numbers = list(map(int,input().split()))
numbers = sorted(numbers)
x = int(input())
first, second = 0,n-1
answer = 0
while True:
if first == second or first > second or second < first:
break
now = numbers[first]+numbers[second]
if now == x:
answer+=1
first+=1
second-=1
elif now < x:
first +=1
else:
second -=1
print(answer)
|
cs |
문제링크:
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]3055. 탈출 (0) | 2021.05.11 |
|---|---|
| [BOJ]2630. 색종이 만들기 (0) | 2021.04.29 |
| [BOJ]9184. 신나는 함수 실행 (0) | 2021.04.22 |
| [BOJ]2981. 검문 (0) | 2021.04.20 |
| [BOJ]10819. 차이를 최대로 (0) | 2021.02.25 |