c언어 2473번 세 용액 (백준)

#include <stdio.h>

int main(void) {
	int n;
	scanf("%d", &n);
	int a[n];
	for(int i=0; i<n; i++) scanf("%d", &a[i]);
	
	int i, j, gap=n/2, key;
	while(1) { //shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<n; i++) {
			key = a[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key < a[j]) a[j+gap] = a[j];
				else break;
			}
			a[j+gap] = key;
		}
		if(gap==1) break;
		gap >>= 1;
	}
	
	long long int min = 3000000001; // 세 용액의 최댓값은 3000000000이므로 long long int로 잡아주어야 합니다.
	int x, b, c, d;
	long long int sum, tmp;
	
	for(x=0; x<n-2; x++) { //첫번째 용액을 하나를 고정한 다음
		int l = x+1;
		int r = n-1;
		while(l<r) {//투 포인터를 사용합니다.
			sum = (long long int)a[l] + a[r] + a[x]; //더하기의 최댓값이 3000000000이며 이는 int의 범위를 벗어나기에, overflow가 뜰 수 도 있습니다. 고로 longlongint 로 캐스팅 합니다.
			tmp = sum;
			if(sum<0) sum *= -1;
			
			if(min > sum) { //세용액의 합의 절댓값이 이전의 절댓값보다 더 작다면 최소를 만들 수 있는 용액들을 새걸로 대입한다.
				min = sum;
				b = a[x];
				c = a[l];
				d = a[r];
				if(sum == 0) break; //만약 0 이라면, 더이상 탐색을 할 필요가 없다.
			}
			
			if(tmp > 0) r--; //세 용액의 합이 양수이면, 오른쪽 포인터를 감소시키며,
			else if(tmp < 0) l++; //세 용액의 합이 음수이면, 왼쪽 포인터를 증가시킨다.

		} if(tmp == 0) break;
	}
	
	printf("%d %d %d", b, c, d); //최소값을 만드는 세 용액을 출력
}

 

풀이 : 투 포인터

 

두 포인터를 이용합니다.

세 개의 용액이 있다면, 하나를 고정시킨 다음 나머지 두 개의 용액을 두 포인터로 돌립니다.

고정시킨 용액은 두 포인터가 끝나면, 다음 용액으로 넘어간 후 다시 두 포인터를 돌립니다.

 

1. 입력을 받습니다.

2. 두 포인터를 사용하기 위해서, 정렬을 합니다 (위의 코드는 shell sort을 했습니다)

3. for문으로 가장 왼쪽에 있는 용액부터 고정키며,  한 개씩 움직이도록 만듭니다.

4. 용액 한개를 고정시키면, 나머지 두 개를 두 포인터로 돌립니다.

4-1. 두 포인터를 움직일 때, 세 용액의 합이 음수이면 왼쪽 포인터를, 양수이면 오른쪽 포인터를 움직입니다.

5. 투 포인터 과정 중, 세 용액의 합이 0이면, 더 이상 탐색할 필요가 없으므로, for문을 멈춥니다.

6. 최소 세 용액의 합을 이루는 용액 세개를 출력합니다.

 

 

ex)

5
-2 6 -97 -6 98

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

2473번: 세 용액