[백준]대홍수(20314)

문제 링크 : [백준]대홍수(20314)

20314번: 대홍수

문제 설명

i번째 지역에서 i+1번째 지역으로 가는데 T_i만큼의 시간이 걸립니다.

i초 후에는 i미터 만큼 물이 차오르기 때문에, i초 후에는 높이가 i미터 미만인 지역으로는 이동할 수 없습니다.

이 때, 각 지역에서 출발하여 이동 할 수 있는 지역 중 최대 높이를 구하세요.

입력

N(지역의 갯 수, 1 <= N <= 200,000)

H_i(지역의 높이, 1 <= H_i <= 100,000,000)

T_i(i번째 지역에서 i+1번째 지역으로 이동하는데 걸리는 시간, 1 <= T_i <= 100,000,000) 

10
3 5 2 8 4 7 6 2 4 4
4 1 2 2 3 2 2 2 1

 

출력

5 8 8 8 8 8 7 7 7 4

 

카테고리

#세그먼트트리 #투포인터

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 각 마을에서 갈 수 있는 마을을 구하고, 그 마을 중 최대 높이를 구해주면 됩니다.
2. 구간의 최대값을 구하기 때문에, 세그먼트 트리를 이용하면 빠르게 구간의 최대값을 구할 수 있습니다.
3. 문제는 각 마을에서 갈 수 있는 범위를 구하는데 브루트포스로 구하게 되면 마을마다 O(N)의 시간복잡도가 나오게 돼서, 총 O(N²logN)의 시간복잡도가 발생합니다.
4. 한 마을에서 왼쪽으로 최대한 갈 수 있는 마을은 계속 이동하면서 걸린 시간이 도착한 마을의 높이보다 작거나 같은동안 계속 갈 수 있습니다.
5. 그리고 그 다음 마을에서 갈 수 있는 마을 또한 4번과 같은데, 이전 마을에서 현재 마을까지 오는데 걸린 시간만큼을 현재 마을에서 더 갈 수 있습니다.
   1. 이전 마을에서 갈 수 있었던 마을이면 현재 마을에서도 갈 수 있습니다.
   2. 이전 마을에서 현재 마을로 오는데 걸린 시간만큼 줄어들기 때문에, 각 마을에 도착할 때 걸린 시간이 줄어들어 물에 잠길 위험ㅇ 없습니다.
6. 이렇게 이전 마을에서 갈 수 있는 오른쪽 최대 마을을 관리하고, 다음 마을들로 이동하면서 포인터를 움직이면 됩니다.
7. 반대로 왼쪽으로 갈 수 있는 마을들도 위와 반대방향으로 진행하며 구해줍니다.
8. 두 방향 중 더 높은 위치를 출력해주면 됩니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#include<algorithm>
#define N 200001
using namespace std;
int n,p,i,d[N],t[N*4],a[N];
long long e[N],s;
int u(int p,int l,int r){
    if(l==r)return t[p]=d[l];
    return t[p]=max(u(p*2,l,(l+r)/2),u(p*2+1,(l+r)/2+1,r));
}
int q(int p,int l,int r,int x,int y){
    if(y<l||r<x)return 0;
    if(x<=l&&r<=y)return t[p];
    return max(q(p*2,l,(l+r)/2,x,y),q(p*2+1,(l+r)/2+1,r,x,y));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>d[i];
    u(1,1,n);
    for(i=2;i<=n;i++)cin>>e[i];
    for(p=i=n;i;i--){
        if(p>i)p=i,s=0;
        while(p>1&&s+e[p]<=d[p-1])s+=e[p--];
        a[i]=q(1,1,n,p,i);
        s-=e[i];
    }
    for(s=0,p=i=1;i<=n;i++){
        if(p<i)p=i,s=0;
        while(p<n&&s+e[p+1]<=d[p+1])s+=e[++p];
        cout<<max(a[i],q(1,1,n,i,p))<<" ";
        s-=e[i+1];
    }
}