전체 용액의 수: N
용액의 특성값의 범위는 광범위한 상태이다.
이를 일일이 확인하면 TLE가 되므로, 이분 탐색이 낫다.
이분 탐색은 왼쪽과 오른쪽을 서서히 중앙으로 모이게 만드는 전략이다.
하지만, 이분 탐색은 두 용액이면 유용하겠지만, 세 용액은 오히려 더 힘든 상태이다.
그래서 사용하는 것이 투 포인터이다.
투 포인터에 관한 설명은 geeksforgeeks에 잘 되어 있다.
https://www.geeksforgeeks.org/two-pointers-technique/
Two Pointers Technique - GeeksforGeeks
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
www.geeksforgeeks.org
import sys
def main():
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
ans = [0, 0, 0]
min_diff = 3000000000
for i in range(N-2):
l, r = i+1, N-1
while l < r:
tmp = arr[i] + arr[l] + arr[r]
if abs(tmp) < min_diff:
min_diff = abs(tmp)
ans = [arr[i], arr[l], arr[r]]
if tmp < 0:
l += 1
else:
r -= 1
print(*ans)
if __name__ == '__main__':
main()
'백준 온라인 저지 싹쓸이' 카테고리의 다른 글
[BOJ16946] 벽 부수고 이동하기 4 (1) | 2022.09.25 |
---|---|
[BOJ16724] 피리 부는 사나이 (1) | 2022.09.25 |
[BOJ4386] 별자리 만들기 (1) | 2022.09.24 |
[BOJ2887] 행성 터널 (0) | 2022.09.24 |
[BOJ 11257] IT 시험 (0) | 2022.09.23 |