반응형
문제
n개의 서로 다른 양의 정수들로 이루어진 수열이 있다. ai + aj= x (1 ≤ i < j ≤ n)를 만족하는 (ai, aj) 쌍의 수를 구하시오.
풀이
정말 쉬운 문제인데 올리는 이유는 자꾸 시간초과가 떠서 이분탐색으로 풀었다..
사실 그냥 sorting해서 index를 앞 뒤로 줄여나가며 탐색하면 끝ㅠ 분발하자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | n = int(input()) arr = sorted(map(int, input().split())) x = int(input()) cnt = 0 i = 0 j = n-1 while i != j : s = arr[i] + arr[j] if s == x : cnt += 1 i += 1 elif s > x : j -= 1 else : i += 1 print(cnt) | cs |
반응형
'0 > algorithm' 카테고리의 다른 글
| Kickstart Round A 2018 Problem A (0) | 2018.11.11 |
|---|---|
| 백준 2644번 촌수계산 (Python) (0) | 2018.11.04 |
| 백준 11501번 주식 (Python) (0) | 2018.11.02 |
| 백준 2042번 구간 합 (Python) (1) | 2018.11.02 |
| 백준 1620번 나는야 포켓몬 마스터 이다솜 (Python) (0) | 2018.11.01 |