티스토리 뷰

Problem Solving/BOJ

[BOJ 2470] 두 용액 C++

유자애옹 2021. 7. 22. 20:48

 

 

2470번: 두 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00

www.acmicpc.net

 

문제풀이

 

용액들의 특성값이 주어졌을 때 두 개의 용액을 선택해서 특성값이 0에 가장 가까운 용액을 찾는 문제다.

 

투 포인터 알고리즘으로 left는 첫번째 인덱스부터, right는 마지막 인덱스부터 탐색해나간다.

diff는 특성값과 0의 차, minx와 miny는 두 용액의 인덱스 정보이다.

 

두 용액의 합이 diff보다 작은 경우 정보를 갱신해준다.

두 용액의 합이 0이라면 특성값이 0에 가장 가까운 용액을 찾은 것이므로 탐색을 종료한다.

sum이 0보다 작으면 arr[left]값이 더 커져야 하므로 left++,

sum이 0보다 크면 arr[right]값이 더 작아져야 하므로 right++ 해준다.

 

 

C++ 코드

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ 2473] 세 용액 C++  (2) 2021.07.22
[BOJ 2467] 용액 C++  (0) 2021.07.22
[BOJ 14921] 용액 합성하기 C++  (0) 2021.07.22
[BOJ 4779] 칸토어 집합 C++  (0) 2021.07.20
[BOJ 4256] 트리 C++/Kotlin  (0) 2021.07.20
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함