baekjoon 2473: 세 용액

https://www.acmicpc.net/problem/2473

2473번: 세 용액

문제를 읽고 알고리즘을 구상 하였을때, 백트래킹문제로 생각을 하고 구현을 하였지만, n의 갯수가 5000까지 간다는점과 제한시간이 1초라는 걸 생각했어야 했다.

---

초기 구현했던 내 문제풀이 방식이다.

n = int(input())
arr = list(map(int,input().split()))
path = ['']*3
used=[0]*n
Min = 21e8
result = []
def dfs(level):
    global Min, result

    if level ==3:
        if Min > abs(path[0]+path[1]+path[2]):
            Min = abs(path[0] + path[1] + path[2])
            result = [path[0],path[1],path[2]]
        return

    for i in range(n):
        if used[i] ==1: continue
        used[i] =1
        path[level] = arr[i]
        dfs(level+1)
        used[i] = 0
dfs(0)
result.sort()
print(*result)

백트래킹을 이용해 0에 가까운 수(절댓값이 0에 가까운 수)를  찾게 끔 구현하였지만, n의 갯수가 커지는 만큼 branch가 커지므로 들어가야 할 길이 너무 많아져 시간초과가 나왔다.

---

 

이후 알고리즘 분류부분을 확인한 후 투포인터, 이진탐색등을 이용해야 된다는걸 깨달음...

n = int(input())
arr = list(map(int,input().split()))
arr.sort()
Min = float("inf")
result = []

for i in range(n-2):
    a3 = arr.pop()
	# 투포인터 진행
    st, ed = 0, len(arr)-1
    while(st != ed):
        Sum = a3 + arr[st] + arr[ed]
        if Min > abs(Sum):
            Min = abs(Sum)
            result = [a3,arr[st],arr[ed]]

        # Sum이 음수인 경우
        if Sum < Min:
            st+=1
        # Sum이 양수인 경우
        else:
            ed -= 1

        if Min ==0:
            break
    if Min ==0:
        break

print(*sorted(result))