[Python] BOJ(백준) 2470번 - 두 용액

링크

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

난이도(solved.ac 참고)

골드5

풀이

이분 탐색 또는 투포인터로 풀 수 있는 문제인데 나는 투포인터로 풀었다. 둘 중에 어느 것으로 풀어도 상관 없을 것 같긴 하다. 이분 탐색을 잘 썼다면 그쪽 코드가 좀더 간결했을 것이다.

 

이 문제의 핵심은 부분합을 계속 구해가면서, 기존에 있던 부분합의 절댓값보다 작은 경우(즉 0에 가까운 경우) 부분합에 들어가는 요소와 그 합을 바꿔주는 방식으로 풀어야 한다는 점이다.

 

우선 배열의 첫번째와 마지막 값, 그리고 그 두개를 더한 값을 ans라는 리스트에 넣었다.

반복문을 도는데, 당연히 시작점과 끝점이 같으면 안되므로 그부분은 반복문에서 먼저 넣어준다.

현재 ans에는 (첫째값, 마지막값, 합)의 형태로 들어가있기 때문에 abs(ans[0][2]), 즉 부분합의 절댓값보다 현재 내가 새로 구한 부분합의 절댓값이 더 작은 경우에 pop해준 뒤에 push해줬다. 그 이후, 그 부분합이 target(이 문제에서는 0에 최대한 가까워져야 하므로 0이다.)보다 작다면 시작점을 +1 해줘서 값을 키웠고, target보다 크다면 끝점을 -1 해줘서 값을 줄였다. 같다면 그자리에서 바로 반복문을 종료해줬다.

 

위 반복문의 과정을 거치고 나면 결국 남는 건 부분합이 0에 가장 가까운 (start, end, 부분합)이므로 여기에서 오름차순으로 배열한다고 했으므로 첫번째 값, 두번째 값을 차례대로 출력하면서 마무리하였다.