[2934]_LRH 식물

LRH 식물

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	571	232	157	47.006%

문제

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 

상근이는 매일 매일 화단에 식물을 하나씩 심는다. 첫 번째 날에 심은 식물의 높이는 1이고, 그 다음날에 심은 식물은 전날에 심은 식물의 높이보다 1 크다.

새 식물의 줄기가 다른 식물의 수평 선분과 교차하는 경우가 있다. 이러한 경우에 그 위치에는 꽃이 하나 피게 된다. (이미 꽃이 있는 경우에는 꽃이 더 피지 않는다) 점에서 접하는 경우에는 꽃이 피지 않는다.

아래 그림은 예제를 나타낸 것이다.

모든 식물의 좌표가 주어졌을 때, 매일 매일 피는 꽃의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 식물을 심은 날의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 매일 매일 심은 식물의 두 줄기 좌표 L과 R이 주어진다. (1 ≤ L < R ≤ 100,000) 

출력

총 N개의 줄에 매일 매일 핀 꽃의 수를 출력한다.

예제 입력 1 

4
1 4
3 7
1 6
2 6

예제 출력 1 

0
1
1
2

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Croatian Regional Competition in Informatics 2009 6번

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Regional Competition - Seniors 4번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: metadata

링크

• Sphere Online Judge

풀이

1. 생각나는대로 풀기 =>  N^2 * logN

- 0번째 라운드(입력1개 들어왔을때) 는 필 꽃이 없으므로 항상 0

- 1번째 라운드(입력2개 들어왔을때)부터는 각 식물마다 뒤에 심겨진 식물들에의해 꽃이 생성될 수 있는지 판단한다. 

  이때 중복된 곳인지 판단할 때는, set을 사용하여 insert가 이루어져 값이 증가했는지로 판단한다.

소스코드

#include <cstdio>
#include <set>
#include <vector>
using namespace std;
 
 
int main() {
    int n; scanf("%d", &n);
    vector<pair<int, int> > v;
    for (int i=0; i<n; i++) {
        int l, r;  scanf("%d%d", &l, &r);
        v.push_back(make_pair(l, r));
    }
    printf("0\n"); // round 0
    set<pair<int, int> > s;
    for (int round = 1; round<n; round++) {        // N
        int ans=0;
        for (int i = 0; i<round; i++) {              // N
            if (v[i].first < v[round].first &&
                v[round].first < v[i].second) { 
                int temp = s.size();
                s.insert(make_pair(i, v[round].first)); // logN
                if (temp != s.size())
                    ans++;
            }
            if (v[i].first < v[round].second &&
                v[round].second < v[i].second) {
                int temp = s.size();
                s.insert(make_pair(i, v[round].second));
                if (temp != s.size())
                    ans++;
            }
        }
        //printf("%d\n", ans);
    }
    printf("끝");
    return 0;
}

※ 라운드(식물들어올때마다) 최대 N번 * 식물 수 N개 * insert시간 logN => N^2 * logN

2. 1차원 배열로 풀기 => N^2

길이가 100001인 배열을 만들고

각 위치에는 새롭게 식물을 심을때 꽃이 피어날 수 있는 개수를 적어둔다.

식물이 새롭게 들어올때,

① 기존의 배열을 보고 꽃이 생성될 수 있는 부분을 구하고, (양 끝의 값 의 합을 출력하고 해당부분 0으로 만들기)(그부분에서는 중복생성안되니깐 생길수있는걸 0으로 만듦)

 ② 식물을 심어 추후에 꽃이 피게 할 수 있는 부분 (양끝빼고 사이의 값)을 +1시켜준다.

ex)        초기                                  0 0 0 0 0 0 0 0 0 0

  1,4 들어옴                      0 0 0 0 0 0 0 0 0 0   // ① 1,4 위치의 값의 합을 출력(0+0)하고 그 값을 0으로 만들어준다. 

                                               0 0 1 1  0 0 0 0 0 0  // ② 1~4(1,2,3,4)에서 양끝(1,4)을 제외한 부분인 2,3위치의 값을 1 더해준다.

  3,7 들어옴                      0 0 0 1 0 0 0 0 0 0   // ① 3,7위치의 값의 합을 출력(1+0)하고 그값을 0으로 만들어준다.

                                        0 0 0 1 1 1 1 0 0 0   // ② 3~7(3,4,5,6,7)에서 양끝(3,7)을 제외한 부분인 4,5,6위치의 값을 1 더해준다.

  1,6 들어옴                      0 0 0 1 1 1 0 0 0 0   // ① 1,6위치의 값의 합을 출력(0+1)하고 그값을 0으로 만들어준다.

                                 0 0 1 2 2 2 1 0 0 0   // ② 1~6(1,2,3,4,5,6)에서 양끝(1,6)을 제외한 부분인 2,3,4,5위치의 값을 1 더해준다.

  2,6 들어옴                      0 0 0 2 2 2 0 0 0 0   // ① 2,6위치의 값의 합을 출력(1+1)하고 그값을 0으로 만들어준다.

                                 0 0 1 3 3 3 1 0 0 0   // ② 2~6(2,3,4,5,6)에서 양끝(2,6)을 제외한 부분인 3,4,5위치의 값을 1 더해준다.

  3,4 들어옴                      0 0 1 0 0 3 1 0 0 0   // ① 3,4위치의 값의 합을 출력(3+3)하고 그값을 0으로 만들어준다.

                                 0 0 1 0 0 3 1 0 0 0   // ② 3~4(3,4)에서 양끝(3,4)을 제외한 부분은 없다.

소스코드

#include <cstdio>
 
using namespace std;
int map[100001];
 
int main() {
    int n; scanf("%d", &n);    
    for (int i=0; i<n; i++) {
        int l, r;  scanf("%d%d", &l, &r);
        
        printf("%d\n",map[l]+map[r]);            
        map[l]=0;
        map[r]=0;
 
        for (int k=l+1; k<=r-1; k++)
            map[k]++;
    }
    return 0;
}

※ 식물수 N번 * 구간에 1씩더하는for문(구간길이는 최대 N) = N^2

3. 2번의 아이디어를 펜윅트리로 구현 => N * logN

만일 펜윅트리에 대해 이해하지 못했다면 먼저 학습을 할 것.

펜윅트리는 구간의 합과 값의 업데이트가 logN만에 이루어질수 있다.

이를 활용하여 2번의 아이디어를 그대로 가져오되, 과정을 최적화하자

즉, 기존에는 map[l], map[r]이런식으로 우리가 알고자 하는 값(현재 그 위치에서 피어날 수 있는 꽃의 수)을 배열의 값에 직접 저장했지만,

처음부터 해당 위치까지의 값을 더했을 때(sum(l),sum(r)이런식으로), 현재 그 위치에서 피어날수 있는 꽃의 수가 되도록 바꿔보자.

★ 아이디어는 동일!

식물이 새롭게 들어올때,

 ① 기존의 배열을 보고 꽃이 생성될 수 있는 부분을 구하고, (양 끝의 값 의 합을 출력하고 해당부분 0으로 만들기)(그부분에서는 중복생성안되니깐 생길수있는걸 0으로 만듦)

 ② 식물을 심어 추후에 꽃이 피게 할 수 있는 부분 (양끝빼고 사이의 값)을 +1시켜준다.

코드를 먼저 보자.

기존코드 printf("%d\n",map[l]+map[r]); //①-1 map[l]=0; // ①-2 map[r]=0; // ①-3 for (int k=l+1; k<=r-1; k++) // ② map[k]++;

새로운 코드 int L = sum(l);  int R = sum(r);  printf("%d\n",L+R); // ①-1 update(l, -L); update(l+1, L); // ①-2 update(r, -R); update(r+1, R);// ①-3 update(l+1, 1);    update(r,-1); // ②

sum(l)은 1번째부터 l번째까지 보면서 각 위치의 값을 다 더한다.

그렇다면 l의 배열 값을  +1로 업데이트(1대입 말고 1더하기) 해준다면( update(l,1) )

sum(l)값과, sum(l+1)값, sum(l+2)값, ...(l이후 부터의 위치에 대한 sum(x)값)은  모두 1씩 증가하게 될 것이다.

그러면 l~r구간까지만 sum값이 1씩 증가하게 하려면 어떻게하면 될까?

매우쉽다. l위치의 값은 1 더해주고 r+1위치의 값을 -1만큼 업데이트 시켜주면(-1대입말고 1빼기) l이후구간은 모두 1씩 증가했다가 r+1구간에서는 -1가 이루어지므로 l~r구간까지의 sum(x)값을 1만큼 증가시킬수 있는 것이다.

(1 말고 아무 수여도 가능)

펜윅트리의 개념을 적용한다면, "현재 그 위치에서 피어날수 있는 꽃의 수"가 sum(x)값이 되도록 

배열의 값을 조정하면 되는 것이다.

(이 때, 배열의 값은 "현재 그 위치에서 피어날수 있는 꽃의 수"를 나타내지 않는다! 

"sum값이 현재 그 위치에서 피어날수 있는 꽃의 수가 되도록 하는" 예를 들면 -1,-2,0,2,1 등과 같은, 각각으로는 의미가 없는 값들이 들어가있을것이다.)

그러면 이전에 (2번째 해결법:N^2)에서 "현재 그 위치에서 피어날수 있는 꽃의 수"가 저장된 배열의 어느 구간의 값을 업데이트 하기위해

 for문을 돌려 배열에 1씩 일일히 더해주던것이 기억나는가?

이것을 위에서 정리한 아이디어를 통해 logN시간(update연산비용)만에 작성할 수 있다.

map[l]=0은 map[l]+= -map[l] 과 같으므로

위에서 정리한 내용에 의해 

update(l,-L); update(l+1,L); // 구간 [l,l]에만 -L더해주기.

update(r,-R); update(r+1,R); // 구간 [r,r]에만 -R더해주기.

update(l+1,1); update(r,-1); // 구간 [l+1,r-1]에만 1더해주기.

소스코드

#include <cstdio>
 
using namespace std;
int map[100001];
 
int sum(int i)
{
    int res = 0;
    while (i > 0)
    {
        res += map[i];
        i -= (i & -i);
    }
    return res;
}
 
void update(int i, int d)
{
    while (i <= 100000)
    {
        map[i] += d;
        i += (i & -i);
    }
}
int main() {
    int n; scanf("%d", &n);
    for (int i=0; i<n; i++) {
        int l, r;  scanf("%d%d", &l, &r);
        // 기존(N^2아이디어)에서 map[l], map[r]로 접근해서 얻어오던 꽃생성될수있는 곳 수를 
        // 펜윅트리에서 sum(l), sum(r)로 접근할수 있도록 함.
        // 그에 맞게 펜윅트리의 배열 값을 조정해주기.
 
        int L = sum(l);
        int R = sum(r);
        printf("%d\n", L+R);
        update(l, -L);    update(l+1, L);
        update(r, -R);    update(r+1, R);
 
        update(l+1, 1);
        update(r, -1);
    }
    return 0;
}
 

배운것 : 어떤 배열에서 일부 구간의 값을 모조리 일정 값 만큼 업데이트 하는 것을 펜윅트리로 시간을 줄일수있다.

이 때, 이전상황에서의 배열 각각의 값은 sum돌렸을때 각각의 결과값으로 구할수 있으며, 이에 맞게 배열값을 조절해준다.