Algospot MEASURETIME

문제 링크입니다: https://algospot.com/judge/problem/read/MEASURETIME

입력하는 숫자의 수가 많기 때문에 삽입정렬을 이용해서 풀 경우 TLE가 발생하지만, 구간합을 간단하게 구할 수 있는 펜윅 트리를 이용해 문제를 해결합니다.

각 원소 A[i]에 대해 A[0..i - 1] 구간에 A[i]보다 큰 숫자가 몇 개 있는지 알게 된다면 옆으로 몇 칸 움직일지 계산할 수 있습니다.

따라서, 각 숫자의 출현 횟수를 저장하는 펜윅 트리를 만들면 AC를 받을 수 있습니다!

#include <iostream>

#include <vector>

using namespace std;

 

//펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을

//빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의

//원소가 전부 0이라고 생각한다

struct FenwickTree

{

        vector<int> tree;

        FenwickTree(int n) :tree(n + 1)

        {

        }

        //A[0..pos]의 부분 합을 구한다

        int sum(int pos)

        {

                 //인덱스가 1부터 시작한다고 생각

                 pos++;

                 int result = 0;

                 while (pos > 0)

                 {

                         result += tree[pos];

                         //다음 구간을 찾기 위해 최종 비트를 지운다

                         pos &= (pos - 1);

                 }

                 return result;

        }

        //A[pos]에 val을 더한다

        void add(int pos, int val)

        {

                 pos++;

                 while (pos < tree.size())

                 {

                         tree[pos] += val;

                         pos += (pos&-pos);

                 }

        }

};

 

//펜윅 트리를 이용해 문제 해결

long long countMoves(const vector<int> &A)

{

        FenwickTree tree(1000000);

        long long result = 0;

 

        for (int i = 0; i < A.size(); i++)

        {

                 result += tree.sum(999999) - tree.sum(A[i]);

                 tree.add(A[i], 1);

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

       

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N;

                 cin >> N;

 

                 vector<int> A(N, 0);

 

                 for (int i = 0; i < N; i++)

                         cin >> A[i];

 

                 cout << countMoves(A) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]