KOI 2010 세용액
https://en.wikipedia.org/wiki/3SUM
https://www.acmicpc.net/problem/2473
https://www.acmicpc.net/problem/2470
3sum problem
주어진 리스트에서 i<j<k이고 a[i] + a[j] + a[k] = X를 만족하는 해가 있는지 찾는 문제.
먼저 주어진 리스트를 정렬한다. O(nlgn)
i를 고정시키고 오른쪽 범위에서 a[j] + a[k] = X - a[i]를 만족하는 해가 있는지를 찾는 문제를 생각해보자. 이 문제는 O(n)에 해결 할 수 있다. a[j] + a[k] > X - a[i]라면 k를 1 감소 시키고 그 외는 j를 1 증가시킨다. 이러면 O(n)에 만족하는 j, k 를 찾을 수 있다. i를 1씩 증가시키면서 모든 구간에 대해 반복하면 최종적으로 O(n^2)에 답을 찾을 수 있다.
https://www.acmicpc.net/problem/2473
https://www.acmicpc.net/problem/2470
3sum problem
주어진 리스트에서 i<j<k이고 a[i] + a[j] + a[k] = X를 만족하는 해가 있는지 찾는 문제.
먼저 주어진 리스트를 정렬한다. O(nlgn)
i를 고정시키고 오른쪽 범위에서 a[j] + a[k] = X - a[i]를 만족하는 해가 있는지를 찾는 문제를 생각해보자. 이 문제는 O(n)에 해결 할 수 있다. a[j] + a[k] > X - a[i]라면 k를 1 감소 시키고 그 외는 j를 1 증가시킨다. 이러면 O(n)에 만족하는 j, k 를 찾을 수 있다. i를 1씩 증가시키면서 모든 구간에 대해 반복하면 최종적으로 O(n^2)에 답을 찾을 수 있다.
댓글
댓글 쓰기