BOJ 3649 로봇 프로젝트(C++)

로봇 프로젝트 성공

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
5 초	128 MB	1192	238	143	18.428%

문제

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ의 단위는 나노미터이다. 블럭의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스에 대해서, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

예제 입력 

1
4
9999998
1
2
9999999

예제 출력 

yes 1 9999999

힌트

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 J번

• 문제를 번역한 사람: baekjoon

링크

• ACM-ICPC Live Archive

알고리즘 분류

• 정렬
• 이분 탐색

 

#include    <cstdio>
#include    <vector>
#include    <algorithm>
#pragma warning (disable : 4996)
 
std::vector<int> parts;
int bs(int num, int s, int e)
{
    int start = s, end = e;
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (parts[mid] == num)  return mid;
        else if (parts[mid] < num)   start = mid + 1;
        else end = mid - 1;
    }
    return -1;
}
 
int main()
{
    int x, n;
    bool flg;
 
    while (scanf("%d", &x) == 1) //입력이 있다면 scanf는 1을 리턴
    {
        x *= 10000000;
        scanf("%d", &n);
        int tmp;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &tmp);
            parts.push_back(tmp);
        }
        std::sort(parts.begin(), parts.end());
        flg = false;
        for (int i = 0; i < parts.size(); ++i)
        {
            int temp = bs(x - parts[i], i + 1, parts.size() - 1);
            if (temp != -1)
            {
                flg = true;
                printf("yes %d %d\n", parts[i], parts[temp]);
                break;
            }
        }
        if (!flg)
            printf("danger\n");
 
        parts.clear();
    }
}

사실 처음에 이런 유형의 문제가 처음이었어서... 이해하기가 어려웠다. 

테스트케이스가 여러개인데 테스트케이스 갯수를 받지 않는 문제라니... 계속 찾다가 질문게시판에서 확인... 

이런 유형의 문제도 있구나.. 라는 것을 알게 되었다. 

입력이 있다면 scanf는 1을 반환하므로 그것을 이용해서 while loop를 작성하였다. 

문제 자체는 크게 어렵지 않았다. binary search를 이용하면 되는 문제였다. 

정렬한 후 첫 번째 부품부터 맞는 부품이 있는지 찾아서 있다면 분명 그 부품이 맞는 부품 중 가장 작은 부품이므로 짝이되는 부품은 가장 클것이다. 

두 수의 차가 가장 큰 짝이 될 것이므로 바로 출력하면 된다.