[투포인터] 같이 눈사람 만들래?(20366)(C++)

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

20366번: 같이 눈사람 만들래?

 

1. 문제 개요

 

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다. 주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

가능한 모든 경우에 대해 탐색하되 이미 탐색이 끝난 부분이나 탐색이 필요하지 않은 경우를 제외하여 시간을 단축하는 문제.

예를 들어, (1,4)와 (2,3)에 대해 비교가 끝난 경우에는 (2,3)과 (1,4)를 비교할 필요가 없다.

 

따라서 이중 루프로 모든 경우를 탐색하게끔 하고, 이중 루프 안의 또 다른 루프 안에서는 투 포인터를 사용해서 값을 비교하게끔한다.

이때 앞서 말했던 것처럼, (1,4)와 (2,3)에 대해 비교가 끝난 경우에는 (2,3)과 (1,4)를 비교할 필요가 없으므로 투 포인터의 경우에는 인덱스 i와 j 사이의 값에 대해서만 수행하도록 한다.

	for(int i=0;i<N-3;i++) {
        for(int j=i+3;j<N;j++) {
            int fix = v[i]+v[j];
            // 투 포인터
            int left=i+1,right=j-1;
            while(left<right) {
                int temp = v[left] + v[right];
                if(abs(temp-fix)<ans) {
                    ans = abs(temp-fix);
                }
                if(temp<fix) left+=1;
                else if(temp>fix) right -= 1;
                else {
                    printf("0\n");
                    exit(0);
                }
            }
        }
    }

 

 

4. 전체 코드

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>

using namespace std;

int main(void) {
    int N;
    vector<int> v;
    scanf("%d",&N);
    
    for(int i=0;i<N;i++) {
        int temp;
        scanf("%d",&temp);
        v.push_back(temp);
    }
    
    sort(v.begin(), v.end());
    
    int ans = 1000000000;
    for(int i=0;i<N-3;i++) {
        for(int j=i+3;j<N;j++) {
            int fix = v[i]+v[j]; // 비교할 대상
            // 슬라이딩 윈도우
            int left=i+1,right=j-1;
            while(left<right) {
                int temp = v[left] + v[right];
                if(abs(temp-fix)<ans)
                    ans = abs(temp-fix);
                if(temp<fix) left+=1;
                else if(temp>fix) right-=1;
                else {
                    printf("0\n"); // 0이 최솟값이므로 탐색을 마치고 종료
                    exit(0);
                }
            }
        }
    }
    
    printf("%d\n",ans);
}