백준 3273_두 수의 합 / Python

문제

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)

출력

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

예제 입력 1 

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1 

3

---

또 조합문제! 

from itertools import combinations

n = int(input())
nums = list(map(int, input().split()))
x = int(input())
nums.sort()
res = 0
for comb in combinations(nums, 2):
  if sum(comb) == x:
    res += 1
print(res)

예상했지만 시간초과...

 

두 수를 더할 때 한쪽이라도 x보다 크면 의미가 없으니 x보다 큰 숫자들을 미리 지워주면 시간이 줄어들까? 

from itertools import combinations

n = int(input())
nums = list(map(int, input().split()))
x = int(input())
nums.sort()
for i, value in enumerate(nums):
  if value >= x:
    nums = nums[:i]
    break

res = 0
for comb in combinations(nums, 2):
  if sum(comb) == x:
    res += 1
print(res)

7%까진 가는거 보니 case하나는 통과했나보다.. 그렇지만 여전히 시간초과,,

 

라이브러리를 그만 포기하고... 백트래킹으로 풀어보겠다..

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
x = int(sys.stdin.readline())
nums.sort()

res = 0
arr = [-1, -1]

def backtracking(num, prev):
    global res
    if num == 2:
        if sum(arr) == x:
          res += 1
        return
    for i in range(prev, n):
        arr[num] = nums[i]
        backtracking(num + 1, i+1)

backtracking(0, 0)

print(res)

global res를 안해주어 좀 헤맸다. arr는 그냥 접근 가능한데 res는 왜 global선언을 해주어야하지?

리스트; 가변객체 -> 함수 내부에서 해당 객체의 내용을 수정하면 전역 변수로 인식됨.

정수; 불변객체 -> 함수 내부에서 값을 변경하려고 하면 새로운 로컬 변수가 만들어짐.

그렇군

 

근데 저 코드는 응.....시간초과.......나보고 어떡하라고. 우뜩하라고. 어떠콰라고. 우르과이라고. 오뚜기라고.

 

 

x보다 큰 숫자들을 미리 지워봐도

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

for i, value in enumerate(nums):
  if value >= x:
    nums = nums[:i]
    break
    
res = 0
arr = [-1, -1]

def backtracking(num, prev):
    global res
    if num == 2:
        if sum(arr) == x:
          res += 1
        return
    for i in range(prev, len(nums)):
        arr[num] = nums[i]
        backtracking(num + 1, i+1)

backtracking(0, 0)

print(res)

시간초과....

 

 

하 도저히 모르겠어서 gpt의 힘을 빌렸더니.. 접근부터가 잘못됐다...

순열이라 백트래킹으로 풀려고 했는데 투포인터였어!! 왜 생각을 못했지!!!!

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

res = 0
l, r = 0, n - 1
while l < r:
  s = nums[l] + nums[r]
  if s == x: #x와 같으면 왼, 오 둘 다 이동
    res += 1
    l += 1
    r -= 1
  elif s < x: #x보다 작으면 왼쪽만 이동
    l += 1
  else: #x보다 크면 오른쪽만 이동
    r -= 1
print(res)

이렇게나 간단한 코드를....하...

x보다 큰 숫자들까지 미리 지우면

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

for i, value in enumerate(nums):
  if value >= x:
    nums = nums[:i]
    break

res = 0
l, r = 0, len(nums) - 1
while l < r:
  s = nums[l] + nums[r]
  if s == x:
    res += 1
    l += 1
    r -= 1
  elif s < x:
    l += 1
  else:
    r -= 1
print(res)

시간이 좀 더 줄었네요~