[Java] BOJ14921_용액 합성하기

www.acmicpc.net/problem/14921

14921번: 용액 합성하기

---

두 용액을 섞어서 0과 가장 가까운 수를 만드는 문제이다. 두 용액을 선택하기 위해 두 포인터 알고리즘을 사용했다.

 

포인터를 양 쪽 끝으로 잡고 두 용액의 합이 음수일 경우 왼쪽 포인터를 증가시켰고 양수일 경우 오른쪽 포인터를 감소시켰다. 값들이 오름차순으로 정렬되어있기 때문에 두 용액을 섞었을 때 0과 가까운 수를 만들기 위함이다.

왼쪽 포인터를 증가시키면 두 용액의 합은 커지고 오른쪽 포인터를 감소시킬 경우 합은 작아진다.

 

이렇게 포인터를 증감하며 합을 구하고 최소값 비교는 절댓값을 사용해서 해야 한다. 0과 가장 가까운 것이 최소이기 때문이다.

출력에서 주의할 점은 절대값을 취하지 않은 값을 출력해야 한다는 것이다.

 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int left = 0;
		int right = N-1;
		int min = Integer.MAX_VALUE;
		while(true) {
			if(left==right) break;
			int sum = arr[left] + arr[right];
			if(Math.abs(sum) <= Math.abs(min)) {
				min = sum;
			}
			if(sum < 0) {
				left++;
			} else {
				right--;
			}
			
		}
		System.out.println(min);
	}
}

 

 

[참고]

거의 같은 문제이므로 한번 풀어보면 좋다.

jihunworld.tistory.com/29

[Java] BOJ2467_용액