[PS] 백준 2517번: 달리기

|

문제

내가 이해한 문제 내용

실력 값들이 차례대로 주어질 때 순서대로, 최선의 등수를 출력하시오.

접근 방식

  • 첫번째 접근: $O(NlgN)$만에 풀어야 하는게 보여서 이분탐색을 시도해 보았지만 도저히 답이 안나옴.
  • 두번째 접근: 힌트를 보고 세그트리라는 것을 안 후에 LIS를 세그트리로 푸는 방법을 응용하려 했으나 실패.
  • 결국 답을 보았고 여기를 참고하였음

어려웠던 점 & 배운 점

세그먼트 트리를 이렇게 활용할 수 있다는 점이 신기했다. 아직 세그트리가 익숙하지 않기 때문에 풀이를 이해하는데도 상당시간이 걸렸다. 많이 어려운 문제라고 생각한다. 참고한 풀이를 쓰신 분의 접근방식은 이러하다.

  • 주어지는 실력 값의 범위가 10억을 넘어가기 때문에 세그트리로 구현하면 메모리 초과가 발생한다.
  • 하지만 $N$의 범위는 50만이므로 실력 값을 상대적인 인덱스 값으로 변환하면 범위를 넘지 않는다.

상대적인 인덱스 값으로 변환하는 방법은 예제에서 2,8,10,7,1,9,4,15가 있는데 이걸 std::pair<int,int>로 숫자,인덱스를 동시에 배열에 저장한다. 그 다음 숫자를 기준으로 정렬하면 1,2,4,7,8,9,10,15가 된다. 이제 각 숫자를 그 숫자에 해당하는 인덱스 값으로 바꾼다. 바꾸면 0,1,2,3,4,5,6,7이 되고 이걸 다시 처음 배열에 저장했던 인덱스 값으로 정렬하면 1,4,6,3,0,5,2,7이 된다.

여기서부터가 중요한데, 얻어낸 값을 세그트리로 그대로 활용한다. 즉, 세그트리의 인덱스 값 그 자체로 활용하는 것이다. $N=8$이므로 세그트리는 0~7, 0~3, 4~7, 0~1, 2~3, 4~5, 6~7, 0, 1, 2, 3, 4, 5, 6, 7 이렇게 노드를 가지게 되는데 각 노드에는 그에 해당하는 개수를 저장하면 된다. 각 노드가 구간에 해당하는 숫자의 개수로 정의하는 것이다.

이렇게 정의하면 세그트리에 쿼리를 날릴 때 특정 값과 함께 날릴 텐데, 구간에 해당하는 값을 보고 특정 값보다 큰 숫자의 개수를 파악할 수 있다. 그렇게 차례대로 $N​$번 반복하면서 쿼리를 날리고 업데이트도 해주면 최선의 등수를 알아낼 수 있다.

시간복잡도

  • 정렬: $O(NlgN)$
  • 세그트리의 쿼리와 업데이트: $O(NlgN)$
  • 최종: $O(NlgN)$

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;

vector<int> tree;
int n;
pii a[500000];

int query(int node,int value,int s,int e)
{
    // 특정 값이 시작인덱스보다 작다는 것은
    // 해당 노드의 값이 더 큰 숫자들의 개수를 의미하므로 그냥 리턴
    if(value<s) return tree[node];

    // 마지막 인덱스보다 크다는 것은 특정 값보다 다 작은 것이므로 신경쓸 필요 없음
    // 시작인덱스=마지막 인덱스인 경우도 위에서 걸려졌기 때문에 신경 ㄴㄴ
    if(value>e || s==e) return 0;
    return query(node*2,value,s,(s+e)/2)+query(node*2+1,value,(s+e)/2+1,e);
}
 
 
int update(int node,int s, int e, int value)
{
    // 범위를 벗어나는 경우 고려하지 않음
    if(s>value || e<value) return tree[node];
    // 특정 값이 들어갈 곳을 찾았다면 개수를 1로 만들어줌
    if(s==e) return tree[node] = 1;
    return tree[node] = update(node*2,s,(s+e)/2,value)+update(node*2+1,(s+e)/2+1,e,value);
}

// pair를 두 번째 값 기준으로 정렬하기 위함
bool cmp(pii a1, pii a2){
    return a1.second<a2.second;
}

int main(void)
{
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",&a[i].first);
        a[i].second = i;
    }

    sort(a,a+n);
    for(int i=0; i<n; i++) a[i].first = i;
    sort(a,a+n,cmp);

    tree.resize(4*n);

    for(int i=0; i<n; i++){
        int ans = query(1,a[i].first,0,n-1);
        printf("%d\n",ans+1);
        update(1,0,n-1,a[i].first);
    }

    return 0;
}