2024. 7. 11. 03:13ㆍ백준
문제
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)
시간이 좀 더 줄었네요~
'백준' 카테고리의 다른 글
백준 15656_N과 M (7) / Python (0) | 2024.07.16 |
---|---|
백준 11478_서로 다른 부분 문자열의 개수 / Python (0) | 2024.07.11 |
백준 15655_N과 M(6) / Python (0) | 2024.07.11 |
백준 1004_어린 왕자 / Python (0) | 2024.07.10 |
백준 2559_수열 / Python (0) | 2024.07.03 |