백준 BOJ 2470 - 두 용액

정보올림피아드 2010년 중등부 1번 문제이다.

중등부 1번을 오래걸리는 능지수준 ㅠ

​

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

2470번: 두 용액

#include <stdio.h>
#include <algorithm>
#include <math.h> 

int arr[100001] = {0};
int n;
long long int min = 2000000001;

int main(){
	scanf("%d", &n);
	
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	std::sort(arr, arr+n);
	int fp=0, ep=n-1; // 두 배열 인덱스 선언. 
	int v1, v2; // 두 용액 선언. 
	while(fp!=ep){
		if(min >= abs(arr[fp]+arr[ep])){
			v1 = arr[fp];
			v2 = arr[ep];
			min = abs(arr[fp]+arr[ep]);
		}
		if(arr[fp]+arr[ep]>0) ep--;
		else if(arr[fp]+arr[ep]<=0) fp++;
	}
	printf("%d %d", v1, v2);
}

배열을 한번 정렬해주고 시작한다.

​

두 인덱스를 저장해주는 fp(front pointer)와 ep(end pointer) 를 만들어줬고,

fp는 가장 작은 숫자를, ep는 가장 큰 숫자의 인덱스값을 가리킬 수 있도록 해주었다.

둘을 더한 합의 절댓값이 최솟값이 0에 가장 가까운 수가 될 것이므로, abs()를 씌워서 최소값과 비교하는 if문이 있고,

​

둘의 합이 양수인 경우에는 둘의 합을 줄여야 하므로,

ep가 가리키는 가장 큰 숫자의 인덱스값을 1 줄여서

둘의 합이 줄어들 수 있게 해주었고,

​

둘의 합이 음수인 경우에는 둘의 합을 늘려야 하므로,

fp가 가리키는 가장 작은 숫자의 인덱스값을 1 늘려서

둘의 합이 늘어날 수 있도록 해주었다.

​

이렇게 하나씩 비교해가며 최솟값을 찾다가, fp == ep 가 되어 둘이 같은 값을 가리키는 경우 프로그램을 종료시키고,

결과를 출력시켜주면 이 문제를 해결할 수 있다.

​

백준에서 풀어낸 첫 골드 문제다.

실력이 조금씩 조금씩 늘고있는것 같긴 하다.

플래/다이아 문제를 풀어내는 그날까지 노동 ON.