[백준] 로봇 프로젝트(3649)

문제 링크 : [백준] 로봇 프로젝트(3649)

문제 설명

주어진 N개의 수 중, 더해서 X를 만들 수 있는 두 수를 고르시오.(여러개라면 두 수의 차이가 큰 것을 출력)

입력

x(구하고자 하는 길이(cm), 1<=x<=20)
n(주어지는 레고의 갯수, 0<=n<=100,000)
D_i(i번째 레고의 길이(nm), 1<=D_i<=100,000,000)
@주의

1. 테스트 케이스가 여러개임.
2. x의 단위는 cm, 레고의 길이 단위는 nm.

1
4
9999998
1
2
9999999

출력

yes 1 9999999

카테고리

#투포인터

시간 복잡도 상한

n이 최대 10만이기 때문에 최대 O(nlogn) 이하로 끝내야합니다.

해결 방법

1. 주어진 레고의 순서는 중요하지 않습니다.(index를 활용하는 곳이 없음)
2. 데이터를 오름차순 정렬한다면,
   2-1. D_i + D_j(i<j)가 x보다 작다면, D_i + D_k (i<k<j)는 항상 x보다 작습니다..
   2-2. D_i + D_j(i<j)가 x보다 크다면, D_k + D_j (i<k<j)는 항상 x보다 큽니다..
3. 2의 특성을 이용하여, i=1, j=n 인덱스부터 시작하고, D_i + D_j(i<j)가
   3-1. x보다 크다면, j를 -1합니다.
   3-2. x보다 작다면, i를 +1합니다.
   3-3. x와 같다면, 그 수를 출력합니다.(이후에 x를 만족하는 값이 있더라도, 두 수의 차이가 최초 나온 수들의 차이보다 항상 작거나 같기 때문에, 더이상 진행할 필요가 없습니다.)

코드

#include<cstdio>
#include<algorithm>
int x,n,d[1000000],i,a;
int main(){
    while(scanf("%d",&x)==1){
        scanf("%d",&n);
        for(i=0;i<n;i++)scanf("%d",d+i);
        std::sort(d,d+n);
        i=0,n--,x*=10000000,a=-1;
        while(i<n){
            a=d[i]+d[n];
            if(a==x)break;
            else if(a<x)i++;
            else n--;
        }        
        if(a==x)printf("yes %d %d\n",d[i],d[n]);
        else printf("danger\n");
    }
}