[백준] 세 수의 합

 

출처:: https://www.acmicpc.net/problem/2295

분류:: 이진탐색 

 

1. 문제 이해 및 해결과정

a + b + c = x  => a + b = x - c : 식을 변형하여 두 수를 조합 하는 형태로 시간 복잡도를 줄일 수 있음

 

 

2. 풀이방법

1) 이진탐색 

import sys
input= sys.stdin.readline

n = int(input())
arr = sorted([int(input()) for _ in range(n)])
plus = sorted([(arr[i] + arr[j]) for i in range(n) for j in range(i, n)])

def exist(x):
    l, r = 0, len(plus)
    while l <= r :
        m = (l+r) // 2
        if plus[m] < x:
            l = m + 1
        elif plus[m] > x:
            r = m - 1
        else :
            return 1
    return 0

flag = False

for i in range(n-1, 0, -1):
    for j in range(i-1, -1, -1):
        if exist(arr[i]-arr[j]):
            print(arr[i])
            flag = True 
            break
    if flag:
        break

 

2) set

import sys
input= sys.stdin.readline

n, m = map(int, input().split())
st = set(input().rstrip() for _ in range(n))

cnt = 0
for x in [input().rstrip() for _ in range(m)]:
    if x in st:
       cnt += 1
print(cnt)

 

3. 오답원인

 

4. 알게된 점