BOJ 7453 합이 0인 네 정수
-
백준 7453 합이 0인 네 정수Algorithm/BOJ 2021. 3. 4. 14:53
출처: www.acmicpc.net/problem/7453 분류: 투 포인터, 이분 탐색 접근방식 4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다. 이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다. a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab, c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd 를 만들고 둘 모두 오름차순으로 정렬해줍니다. 다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다. ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다. sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다..