[백준, 파이썬, 3273번] 두 수의 합

 

풀이

 

• 처음 접근한 방법은 조합을 활용한 방법으로
  • 아래 메모리 초과 코드로서 문제가 의도한 접근 방법이 아니였다..
• 이후 접근한 다른 방법으로는
  • 아래 시간 초과 코드
  • li를 오름차순 정렬 후 2중 for 문을 활용해서 
  • 이전 값과는 비교하지 않는 형식으로 시간과 메모리를 줄여봤지만
  • 여전히 시간초과...
• 그래서 마지막으로 해당 시간을 줄이기 위해
  • 이분 탐색을 적용해서 풀어본 결과 
  • 무사히 제출이 되었다.
  • 이분 탐색 코드는 거의 똑같다고 보면 되기에 설명은 생략함.

 

정답 코드

import sys

input = sys.stdin.readline

n = int(input())

li = sorted(list(map(int,input().rstrip('\n').split())))

x = int(input())

result = 0

for i in range(n):

    s = i+1

    e = n-1

    while e>=s and n-1>=i:

        moc = (s+e)//2

        check = li[i]+li[moc]

        if check == x:

            result += 1

            break

        elif check > x: e = moc-1

        else: s = moc+1

print(result)

 

메모리 초과 코드

import sys

from itertools import combinations

input = sys.stdin.readline

n = int(input())

li = list(map(int,input().rstrip('\n').split()))

x = int(input())

result = 0

for i in list(combinations(li,2)):

    if sum(i) == x: result += 1

print(result)

 

시간 초과 코드

import sys

input = sys.stdin.readline

n = int(input())

li = sorted(list(map(int,input().rstrip('\n').split())))

x = int(input())

result = 0

for i in range(1,n):

    for j in range(0,i):

        if li[i]+li[j] == x:

            result += 1

            break

print(result)