조합, 아이디어 훈련

문제

N개의 샘플이 있고 각각의 샘플에는 정수가 주어진다.

연구를 위해 N개중 2개의 샘플을 채취한다. 이때 샘플이 가진 정수의 합이 0에 가까운 2개의 샘플을 채취하고자 한다.

N(2~100000), 정수A(-1000000 ~ +1000000) 이며 샘플의 정수 값으 오름차순으로 입력된다고 한다.

0에 가까운 값이 여러 경우일 경우 가장 빠른 번호의 샘플을 답으로 한다.

위 조건에 맞는 2개의 샘플 번호를 구하라

 

입력

5

-102 -58 59 78 101

 

출력

0 4

---

문제해결

조합 문제이다. N개의 샘플중 2개의 샘플을 고른다. 순서는 상관이 없다. 트리를 구성하는 DFS로 모든 경우의 수를 수행할 수도 있지만 N이 10만개이므로 시간복잡도 N제곱으로 timeout일 경우가 생긴다. 따라서 DFS는 적절하지 않다.

각각의 index를 모두 비교하는 이중 for문 역시 마찬이다.

이러한 문제는 아이디어를 찾고 규칙을 찾아야한다. 샘플 정수의 합이 0에 가까운 것이 정답이므로 샘플 정수의 합이 2일 경우보다 -1일 경우가 정답이다. 따라서 합의 절대값을 구해야한다.

또한 샘플은 오름차순으로 정렬되어 있다. 이를 토대로 idx를 Head와 Tail에 두어 i, j라고 하자.

Head는 샘플중에 가장 작은 수이므로 Head가 증가할 수록 이전보다 큰값을 만나게 되며

Tail은 샘플중에 가장 큰 수이므로 감소할 수록 이전보다 작은 값을 만나게 된다.

이때 샘플 정수의 두합이 음수일때는 Head가 Tail보다 절대값이 더 큰 경우이다. 그렇기 때문에 0에 가까워 지기 위해서는 Head를 증가시킨다.

반대로 정수의 두합이 양수일떄는 Head보다 Tail의 절대값이 더 큰 경우이므로, Tail을 감소시킨다.

이를 Head와 Tail이 만날때까지 반복시킨다.

 

아래와 같이 입력을 표현할 수 있겠다.

요약하면

0) 절대값이 작을 수록 답을 갱신한다.

1) 두 idx의 정수 합이 양수라면 j를 감소시킨다.

2) 음수라면 i를 증가시킨다.

3) i==j까지 반복한다.

 

#include <stdio.h>

int N;
int A[100000+100];
int idx1;
int idx2;

void Input(){
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d",&A[i]);
	}
}

int ABS(int x)
{
	return x>0 ? x : -x;
}

void Solve(){
	int i=0;
	int j=N-1;
	int diff;
	diff=(int)2e25;
	while(1){
		if(i==j) break; //종료 조건
		if(ABS(A[i]+A[j])<diff)
		{
			diff=ABS(A[i]+A[j]);
			idx1=i;
			idx2=j;
		}
		
		if(A[i]+A[j]==0) //최상결과
		{
			idx1=i;
			idx2=j;
			break;
		}
		//음수면 i를 증가
		else if(A[i]+A[j] < 0) i++;
		//양수면
		else	j--;
	}
}

int main() {
	Input();
	Solve();
	printf("%d %d", idx1, idx2);
	return 0;
}