CF 1041D Glider

Codeforces 1041D glider

문제보러가기

이 문제는 비행기 내에서 주어지는 높이와 임의의 시작점에서 종이 비행기를 던지는데 해당 종이비행기가 비행할 수 있는 최대인 거리를 찾는 문제이다.

비행기가 임의의 점을 비행할 때 종이비행기를 던지면, 항상 하강하며 앞으로 나아가는데 이 때, 특정 구간에서는 하강을 하지 않고 앞으로 갈 수 있다는 것이다. 특정 구간에는 상승기류가 있다고 하자.

즉, 종이 비행기가 날라갈 수 있는 최대인 거리를 찾기위해서는 상승 기류 구간을 잘 고려한다음 x좌표 (1 ~ 1e9) 사이의 점을 골라 던져야 한다는 것이다.

나는 그렇게 똑똑한 사람이 아니기 때문에 먼저 브루트포스하게 찾아보려고 했다. 아마 브루트 포스하게 접근하다보면 솔루션이 보이겠지. 라고 생각했다.

이 문제의 흥미로운 점은, 브루트 포스하게 접근 하는 것 또한 코드가 깔끔하게 짜기가 좀 껄끄럽다는 점이다. 왜냐하면 단순하게 브루트포스하게 짜려고 해도 우선은 그리디 한 접근이 우선되어야했다.

다음을 생각해보자.

Q1 정말 브루트포스하게 하려면 (1 ~ 1e9) 모든 점에서 종이비행기를 던져봐야하나?

YES, but....

던져진 종이비행기는 상승기류 구간 아닐 시 항상 하강하며 앞으로 나아간다.  상승기류일 시 해당 높이를 유지하면서 날아갈 수 있다. 아래의 그림을 보고 추론해보자. 0 부분이 상승기류이다. 상승기류가 아닌 - 곳에서 던지는 것은 의미가 있을까? 최대한 앞으로 나아가야지만 그다음 상승기류를 만날 여지가 있다. 따라서 최대한 0 구간 시작점에 맞춰서 던져서 최대한 앞으로 나아가게끔 만드는 것이 합리적이다.

예제그림>  ----0000-----0000------00000---

따라서, 주어지는 상승기류 구간 시작지점 갯수만큼을 종이비행기를 던지는 장소라고 생각하면 되겠다. 즉, 1e5 개다.

상당히 좋은 크기의 숫자 인 것 같다. 아래는 전 탐색에 사용한 나의 소스이다.

http://codeforces.com/contest/1041/submission/43036054

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

using namespace std;
int a[(int)2e5], b[(int)2e5];

int main()
{
    int n, h; scanf("%d %d", &n ,&h);
    for (int i=0; i<n; i++)
    {
        scanf("%d %d", &a[i], &b[i]);
    }

    int ans=0;
    int i;
    for (i=0; i<n; i++)
    {
        int nowx = a[i];
        int nowh = h;

        int j=i+1;
        while(j<n && a[j] -b[j-1] < nowh )
        {
            nowh = nowh - a[j] + b[j-1];
            nowx = a[j];
            j++;
        }

        if ( nowh>0) nowx = nowx + (b[j-1]-nowx+ nowh);

        if (nowx-a[i]> ans) {
            ans=nowx-a[i];
        }
    }
    printf("%d\n", ans);
}

[0, n) 구간에서 던져보는 것을 구현했다. a[i], b[i]는 각각 i번째 상승기류 시작점과 끝점이다. 시작 때의 x좌표는 a[i] 일것이며, 높이는 초기 높이 h 일것이다.

그 뒤 나는 어떤 것을 셈할 것이냐면, 현재 상승기류 시작점서부터 다음 상승기류 시작점 까지 갈 수 있는지를 먼저 체크한다. j는 다음 상승기류이고, a[j] - b[j-1] 은 다음 상승기류 시작점과 그 전 상승기류 종점 간의 거리를 나타내며, 즉 비행기가 하강하며 전진하는 길이를 나타낸다. 다음 상승기류 시작점 지점 a[j]까지 가려면 높이가 적어도 a[j] -b[j-1] 이상이 되어야 충분히 도착한다고 보장할 것이다. (이 때 j-1 번째 상승기류 a[j-1] 과 b[j-1] 간의 길이는 상관이 없다. )

while 문을 탈출하고 보면, 정확히 j-1 까지의 상승기류는 탈 수 있다고 확언 할 수 있다. 그리고 현재 x의 위치 nowx(=a[j-1])에서  b[j-1] - a[j-1] + nowh 만큼 정확히 이동할 수 있다. 따라서 nowx = nowx+ b[j-1] -a[j-1] +nowh 를 해준다.

그리고 nowx - a[i] 의 거리가 정답보다 길면 정답으로 넣어준다.

충분한 높이에서 던진다고 할 때 최악의 연산은 n+ n-1 + n-2 .... + 1 이므로, 이 소스의 시간복잡도는 O(n^2)이다. 저 소스는 TLE가 났다. 여기가 나의 최선이였다.

Q 2 어떻게 더 시간복잡도를 줄일 수 있을까?

튜토리얼에서는 이분탐색을 제시해주었지만, 이해가 가지 않아 baekjoon slack에서 질문을 한결과 portableangel님께서 답변을 해주셨다. 

"도달 할 수 있는 j는 항상 증가하기만 하며, 줄일 필요가 없다" 라는 것이 답변의 요지였다. 그러므로 j가 증가하는 n + i가 증가하는 n 즉 O(2n) = O(n) 시간복잡도로 문제를 해결 할 수 있었다. 튜터리얼보다 좋은 시간복잡도 이다. 

풀어서 이야기하자면,

사실 정답은 소스안에 있었다. 우리가 이전 i-1에서 시작한 탐색에서 찾은 최대한 갈 수 있었던 상승기류 시작지점 j-1이 있다고 하자. 이제 i번째에서 탐색한다고 했을 때, j의 시작점을 i+1로 다시 땅겨올 이유가 있을까? 

왜냐하면 새로시작하는 지점 i에서 이전 최대 탐색지점 j-1까지 도달 할 수 있다는 것은 당연하다. 왜냐하면 이전 탐색에서, j-1 지점에서 i까지 보다 더 먼 j-1 지점에서 i-1 까지 도달이 가능했기 때문이다.

i와 i-1 사이의 상승기류 구간길이에 영향이 없는 것이, 상승기류는 항상 종이비행기를 제 높이 수준 유지할 수 있기만 해주기 때문에, 어쨌든 새 시작지점 i에서 이전에 도달한 최대 j-1 까지 도달 할 수 있다.

따라서, i에서는 j-1에 있다고 가정하고 j-1초과 즉, j 부터 검사해주면된다. 이 때, 시작 위치는 a[i] 이지만 a[j-1]에 와있다고 가정하므로 높이를 보정해줘야하는데 원 높이 에서 상승기류 구간을 제외한 a[i] 에서 a[j-1] 까지의 길이를 빼면 된다. 이 것을 구하기 위해 prefix sum 을 이용하면 O(1) 만에 접근할 수 있다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/1041D.cc

필요한건 다 쓴거 같은데 말이 너무 긴것같드아..... 나의 수준... ㅠㅠ.. 이 낮아서그렇듯