투포인터
-
[JAVA] 백준 2473 세 용액알고리즘 공부/문제 풀이 2021. 11. 4. 22:40
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net - 처음에는 조합이나 백트래킹을 떠올렸는데 5000이라는 범위가 시간초과가 날 것 같았다. - 투포인터는 O(N)으로 두 가지를 고를 수 있다는 것을 알고, 한가지 용액과 나머지 두 용액을 고르는 것으로 문제를 해결하였다. - 처음에는 투 포인터를 전체 범위에 대해 진행하였지만, i+1 ~ N-1에 대해서만 두 용액을 찾으면 된다는 것을 뒤늦게 깨달았다. 왜냐하면 이미 한 용..