[ 백준 1280 ] 나무 심기 (C++)

백준의 나무심기(1280) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

먼저 구하고자 하는 값들을 어떻게 구할 수 있는지 알아보고 어떻게 접근했는지 알아보자.

다음과 같은 형태로 나무가 주어졌다고 생각해보자.

.

위와 같이 1번부터 5번 나무가 각각 좌표 { a, b, c, d, e } 에 위치해 있을 때, x좌표에 빨강색 X로 표시된 나무를 심어보자.

문제에서 주어진 거리를 구하는 공식에 의하면, X좌표에 나무를 심는데 드는 비용은

(x - a) + (x - b) + (x - c) + (d - x) + (e - x) 가 된다. 그럼 이번에는 한번에 계산하지 말고, 현재 심으려는 나무보다 상대적으로 "앞쪽에 있는 나무들" 과 "뒤쪽에 있는 나무들"로 나눠서 생각을 해보자.

상대적으로 앞쪽에 있는 나무들(파랑색으로 표시된 나무들)과 심으려는 나무(빨강색으로 표시된 나무)의 거리를 구해보자.

그럼, (x - a) + (x - b) + (x - c) 가 될 것이고, 이 식을 정리를 한번 해보자면, 3 * x - (a + b + c) 가 된다.

그럼 아래의 그림은 어떻게 될까 ?

.

이 위의 그림에서도, 심으려는 나무(빨강색으로 표시된 나무) 앞쪽에 있는 나무들의 거리를 한번 구해보자.

그럼, (x - a) + (x - b) + (x - c) + (x - d) 가 될 것이고, 이를 정리해보면, 4 * x - (a + b + c + d) 가 된다.

이제 위에서 구한 2가지 상황을 토대로 "심으려는 나무보다 상대적으로 앞쪽에 있는 나무들간의 거리를 구하는 방법"을 일반화 시켜보면, "심어져 있는 나무의 갯수 * 심으려는 나무의 좌표 - (심어져 있는 나무들의 좌표의 합)" 이 된다.

두 번째로는 상대적으로 뒤쪽에 있는 나무들의 거리를 구해보자.

.

이 경우에는 (d - x) + (e - x) 가 될 것이고, 정리해보면 (d + e) - 2 * x 가 될 것이다.

.

아까와 마찬가지로 한 가지 더 구해보자.

위의 경우에는, (c - x) + (d - x) + (e - x) 가 될 것이고, 정리해보면 (c + d + e) - 3 * x 가 될 것이다.

이 식들을 토대로 "심으려는 나무보다 상대적으로 뒤쪽에 있는 나무들간의 거리를 구하는 방법"을 일반화 시켜보면,

"(심어져 있는 나무들의 좌표의 합) - 심어져 있는 나무의 갯수 * 심으려는 나무의 좌표" 가 된다.

이제 위에서 구한 2개의 식을 적용시켜서 구현만 하면 되는데, 본인은 이 과정에서 '펜윅트리'를 이용해서 구현하였다.

먼저, 펜윅트리에 대해서 잘 모른다면 아래의 글을 읽고 나서, 구체적인 구현 방법에 대해서 알아보자.

[ 펜윅트리 알아보기(Click) ]

펜윅트리는 '누적연산(0번 Index부터 k번 Index까지의 연산)' 을 이용해서 구간에 대한 연산 결과를 빠르게 구할 수 있는 자료구조이다. 위에 문제에는 이 펜윅트리를 다음과 같이 적용시켜볼 수 있다.

1. 현재 심으려는 나무의 좌표보다 상대적으로 앞쪽에 있는 나무의 갯수 구하기.

     - 0번 Index부터 현재 심으려는 나무의 좌표까지 몇 개의 나무가 있는지 구하기.

2. 현재 심으려는 나무의 좌표보다 상대적으로 뒤쪽에 있는 나무의 갯수 구하기.

     - 0번 Index부터 가장 마지막 Index까지의 나무의 갯수를 구한 후, 0번 Index부터 현재 심으려는 나무의 좌표까지 있는 나무의

       갯수만큼 빼버리면 나무의 갯수를 구할 수 있다.

3. 현재 심으려는 나무의 좌표보다 상대적으로 앞쪽에 있는 나무들의 좌표의 합을 구하기.

    - 0번 Index부터 현재 심으려는 나무의 좌표까지 있는 나무들의 거리를 구하기.

4. 현재 심으려는 나무의 좌표보다 상대적으로 뒤쪽에 있는 나무들의 좌표의 합을 구하기.

    - 0번 Index부터 가장 마지막 Index까지의 나무들의 좌표의 합을 구한 후, 0번 Index부터 현재 심으려는 나무의 좌표까지 있는  

      나무들의 좌표 합만큼 빼버리면, 상대적으로 뒤쪽에 심어져 있는 나무들의 좌표 합을 구할 수 있다.

이렇게 적용시킬 수 있다. 그래서 2개의 펜윅트리를 이용해서 위의 과정을 구현하였다.

하나는 "나무의 갯수를 관리하는 펜윅트리" 이고, 또 하나는 "나무의 좌표들의 합을 관리하는 펜윅트리" 이다.

구현의 대부분은 위에 펜윅트리의 설명과 비슷하다. 다만, 주의해야 할 것은, 주어진 나무의 갯수들을 순차적으로 심으면서 그 거리를 구해야 하기 때문에, 심는 순간 Update가 필요하다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 200010
#define MODULER 1000000007
typedef long long ll;
using namespace std;
 
int N;
int Arr[MAX];
vector<int> Cnt_FenwickTree;
vector<ll> Dist_FenwickTree;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a; a++;
        Arr[i] = a;
    }
}
 
void Update_Cnt(int Pos)
{
    while (Pos <= MAX)
    {
        Cnt_FenwickTree[Pos] = Cnt_FenwickTree[Pos] + 1;
        Pos = Pos + (Pos & -Pos);
    }
}
 
void Update_Dist(int Pos, int Value)
{
    while (Pos <= MAX)
    {
        Dist_FenwickTree[Pos] = Dist_FenwickTree[Pos] + Value;
        Pos = Pos + (Pos & -Pos);
    }
}
 
int Query_Cnt(int Pos)
{
    int Result = 0;
    while (Pos > 0)
    {
        Result = Result + Cnt_FenwickTree[Pos];
        Pos = Pos - (Pos & -Pos);
    }
    return Result;
}
 
ll Query_Dist(int Pos)
{
    ll Result = 0;
    while (Pos > 0)
    {
        Result = Result + Dist_FenwickTree[Pos];
        Pos = Pos - (Pos & -Pos);
    }
    return Result;
}
 
void Solution()
{
    Cnt_FenwickTree.resize(MAX + 1, 0);
    Dist_FenwickTree.resize(MAX + 1, 0);
 
    Update_Cnt(Arr[1]);
    Update_Dist(Arr[1], Arr[1]);
 
    ll Answer = 1;
    for (int i = 2; i <= N; i++)
    {
        ll Left_Cnt = Query_Cnt(Arr[i] - 1);
        ll Right_Cnt = Query_Cnt(MAX) - Query_Cnt(Arr[i]);
        ll Left_Dist = Query_Dist(Arr[i] - 1);
        ll Right_Dist = Query_Dist(MAX) - Query_Dist(Arr[i]);
        
        ll Left_Result = Arr[i] * Left_Cnt - Left_Dist;
        Left_Result = Left_Result % MODULER;
        ll Right_Result = Right_Dist - Arr[i] * Right_Cnt;
        Right_Result = Right_Result % MODULER;
 
        ll Result = (Left_Result + Right_Result) % MODULER;
        Answer = Answer * Result;
        Answer = Answer % MODULER;
 
        Update_Cnt(Arr[i]);
        Update_Dist(Arr[i], Arr[i]);
    }
    cout << Answer % MODULER << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}