ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • CF 1041D Glider
    알고리즘 문제/sort, search 2018. 9. 20. 05:44

    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


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

    '알고리즘 문제 > sort, search' 카테고리의 다른 글

    codeforces 283 div2 d tennis game  (0) 2019.11.02
    CF 1041D Glider  (0) 2018.09.20
    888E : Maximum Subsequence  (0) 2017.11.12
    Codeforces : Ordering Pizza  (0) 2017.10.02

    댓글 0

Designed by Tistory.