c언어 2467번 용액 (백준)

#include <stdio.h>

int ab(int x) {
	if(x < 0) return -x;
	return x;
}

int main(void) {
	int n;
	scanf("%d", &n);
	int a[n];
	for(int i=0; i<n; i++) scanf("%d", &a[i]); //용액의 값 입력받기
	
	int l=0, r = n-1; //왼쪽포인터, 오른쪽포인터 설정
	int min = 2000000000;
	int c, d;
	
	while(l<r) {
		int tmp = a[r] + a[l]; // 두 용액의 합
		if(tmp < 0) tmp *= -1; //두 용액의 합의 절댓값
		if(min > tmp) { //현재 최솟값보다 작으면, 치환한다.
			min = tmp;
			c = a[l]; //왼쪽 포인터의 값
			d = a[r]; //오른쪽 포인터의 값
            if(!tmp) break; //만약 최솟값이 0이라면, 더이상 탐색할 필요가 없다.
		}
		
		if(ab(a[r]) < ab(a[l])) l++; //절댓값으로 보았을 때, 오른쪽이 작으면 왼쪽포인터를 오른쪽으로 옮긴다.
		else r--; //반대론, 오른쪽을 왼쪽으로 옮긴다.
	}
	printf("%d %d",c ,d);
}

 

풀이 : 두 포인터

1. 입력을 받는다.

2. 왼쪽, 오른쪽 포인터를 설정한다.

3. 왼쪽 포인터, 오른쪽 포인터가 가르키는 용액을 더한 다음, 그것의 절댓값을 구한다

4. 기존의 최소 절댓값보다 지금 절댓값이 더 작으면, 바꾸어 준다.

5. 만약 용액을 합쳤을 때 0이 나오면, 더이상 탐색을 하지 않아도 된다.

6. 만약 오른쪽 포인터의 용액의 절댓값이 왼쪽 포인터의 용액의 절댓값보다 더 작다면, 왼쪽 포인터를 오른쪽으로

7. 반대라면 오른쪽 포인터를 왼쪽으로 옮김니다.

8. 두 포인터가 겹치면 반복문을 종료합니다.

9. 용액의 합의 절댓값이 가장 적을 때의, 두 개의 용액을 출력합니다.

 

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

2467번: 용액