목록2025/05/30 (1)

민규의 흔적

[C++] 백준 2467번 - 용액

2025년 5월 30일문제 링크 : 백준 2467번 - 용액 문제 접근 오름차순으로 각 용액의 특성값이 주어지는데, 두 용액을 선택해 특성값을 더했을 때 0에 가장 근접하는 두 용액의 특성값을 출력하면 되는 문제이다. 만약 그러한 두 용액 쌍이 2개 이상 존재할 경우 아무 용액 쌍이나 출력해도 된다. 모든 용액 쌍을 구해 각 합에 절댓값을 씌워 0에 가장 가까운 용액 쌍을 출력하는 단순한 방식은, N 이 용액의 개수일 때 시간복잡도 O(N^2)을 가지게 된다. 용액의 개수가 최대 100,000이므로 시간 초과를 범할 것이기에 적절하지 않은 방식이다. 이에 나는 투 포인터를 활용해 포인터를 적절하게 움직여 O(N) 시간복잡도를 가지는 알고리즘 설계를 고안했다. 시도 1 (예외가 발생하는 틀린 풀이)(올바른..
BOJ 2025. 5. 30. 13:18
이전 Prev 1 Next 다음