[BOJ] 3649 로봇 프로젝트

로봇 프로젝트

클릭시 이동합니다.

어떻게 풀까?

정렬 문제라고는 되있지만, 저는 다르게 풀었습니다. 왜냐하면! 답이 10^8을 넘지 않기 때문에, bool 배열을 충분히 만들 수 있기 때문이죠!

구멍의 크기는 입니다.

nm = 

즉, nm = 이라는 것이죠!

구멍을 막기 위해서 필요한 두 블록 중 하나가 l이라고 한다면, 필요한 나머지 하나의 블록은 x - l 일 것입니다!

따라서, 입력을 받을 때 x-l의 블럭이 존재한다면, 구멍을 막을 수 있다는 것이겠죠!

하지만, 문제에 또 다른 조건이 있습니다. 바로 절대값이 가장 큰 수를 출력해야 한다는 것이죠!

절대값이 크기 위해서는 두 수의 차이가 가장 커야하고, 작은 수를 기준으로 보면, 가장 작은 길이 l과, x - l 의 값이 정답으로 출력하면 됩니다. l을 입력받고, x-l이 있다면, l과 x-l중 작은 것을 가장 작은 것을 저장하는 min과 비교해서 가장 작게 유지합시다.

그렇게 하면 마지막에 min과 x-min을 출력하면 원하는 정답을 얻을 수 있을 것 입니다!

그리고, 블럭의 크기가 100000000을 넘지 않기 때문에, 만약, x-l이 100000000을 넘는다면 그냥 넘어가는 동작이 필요하겠죠! 

배열의 크기를 초과하니까요!

그럼, 알고리즘을 정리하겠습니다.

1. l을 입력받습니다.

2. x-l이 100000000보다 작다면,  x-l 이 있는지 check 배열을 확인합니다. 

3. x-l이 있다면, l과 x-l 중 작은 값을 min 값과 비교해서 min에는 항상 작은 값이 들어오도록 합니다.

4. check[l]을 true로 바꿔줍니다.

5. 모든 블록을 입력받으면, min과 x-min을 출력합니다.

코드

#include<cstdio>
#include<cstring>
bool check[100000010];
 
int main() {
    int x;
 
    while (scanf("%d\n", &x) != EOF) {
        x *= 10000000;
        int res = 0x7fffffff;
        int n;
 
        memset(check, 0, sizeof(check));
        
        scanf("%d\n", &n);
        while (n--) {
            int in;
            scanf("%d\n", &in);
 
            if (in < x) {
                if (x - in <= 100000000 && check[x - in]) {
                    int temp = in < x - in ? in : x - in;
                    res = res < temp ? res : temp;
                }
 
                check[in] = true;
            }
        }
 
        if (res == 0x7fffffff) printf("danger\n");
        else printf("yes %d %d\n", res , x - res);
    }
    return 0;
}

여담

시간 복잡도는 O(N) 입니다