BOJ 14870 - 조개줍기

문제 링크 : https://www.acmicpc.net/problem/14870

문제 태그

DP, Two pointer, Segment Tree

문제 풀이

일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. 
$DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$
여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다.

만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 
여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서 업데이트되는 부분은 한개의 구간이라는 것이다. 

즉 왼쪽과 같은 그림의 위치가 업데이트 되는 것은 불가능하며, 오늘쪽과 같이 쭉 붙은 구간이 업데이트가 된다는 것이다. 그 이유는  $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀐다는 데에 있다. 이 부분에 대해서는 좀 생각을 해 보는 것이 좋을 것이다. 

여기서 한 가지 관찰을 더 해보자. 각 칸은 오른쪽과 아래로 영향을 주게 된다. 따라서 i번째 줄에 대해서 업데이트 되는 구간의 왼쪽 끝을 $L_i$라고 하고 오른쪽 끝을 $R_i$라고 하면 $j>i$일때 $L_i\leq L_j \leq R_i\leq R_j$ 라는 순서 관계가 성립하게 된다. 

위의 두가지 관찰을 끝내고 처음 생각한 풀이는 Lazy Segment Tree와 이분탐색을 쓰는 풀이였다. 각 줄별로 dp값을 담고 있는 세그 트리를 만들어 놓고, 이분 탐색을 통해 그 줄에서의 그 위치가 업데이트가 되는지 안되는지를 구해서 시작점과 끝 점을 구한다. 그 다음 구한 구간을 통해 세그 트리에 실시간으로 업데이트를 하면 될 것 같았다. 이때 시간 복잡도는 $O(N^2lg^2N)$ 에다가 lazy를 쓰기 때문에 좀 더 좋은 아이디어가 필요했다.

1. 구간 업데이트와 점 쿼리는 항상 점 업데이트와 구간쿼리로 바꿀 수 있다. 위와 같은 경우도 i번째 세그먼트 트리의 j번째 위치에 dp[i][j]를 저장하고 있는 것이 아니라 dp[i][j]-dp[i][j-1]을 저장시키면 된다. 그리고서는 바뀌는 시작 부분에 1을 더하거나 빼고, 바뀌는 끝부분에 반대를 해주면 된다. 

2. 두번째 관찰을 잘 활용하자. L값은 항상 증가하고, R값도 항상 증가한다. 따라서 그냥 sweeping을 해주면 각 줄 별로 $O(lgN)$이 아니라 전체를 $O(N)$에 해결할 수 있다. 

그러면 이제 가장 중요한 것은 i,j 에 대해서 DP[i][j]의 값은 변화하는가? 에 대해서 답을 해야할 차례이다.
 전 줄에 대해서 업데이트 되는 구간의 왼쪽을 f1, 오른쪽을 f2라고 하자. 그러면 이번 줄에 대해서 새로운 f1'과 f2'를 구해야 한다. 새로운 f2'를 생각해보자. 같은 줄에서는 업데이트가 되는 중간에 껴있는 중이고 아래줄에서의 그 위치는 업데이트가 끝난 위치이다. 따라서 DP[i-1][j]+arr[i][j]가 DP[i][j]$\pm $1 보다 크면 업데이트가 되지 않는 위치이고, 그렇지 않으면 업데이트가 되는 위치이다. 
 그 반대로 f1'에 대해서는 같은 줄에서는 업데이트를 안해놓고 아랫 줄은 업데이트가 되는 칸이기 때문에
DP[i-1][j]+arr[i][j]가 DP[i][j] $\pm $1보다 크면 업데이트가 되는 위치이고 그렇지 않으면 업데이트가 안되는 위치이다. 따라서 새로운 f1'과 f2'을 구하고 이에 맞춰서 업데이트를 해주면 전체 시간복잡도 $O(N^2lgN)$ 에 해결할 수 있다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;


struct SEG{
	ll tree[4100];
	void upt(ll idx,ll val,ll s,ll e,ll nod){
		if(idx<s||idx>e) return;
		tree[nod]+=val;
		if(s==e) return;
		upt(idx,val,s,(s+e)/2,nod*2);
		upt(idx,val,(s+e)/2+1,e,nod*2+1);
	}

	ll sol(ll l,ll r,ll s,ll e,ll nod){
		if(r<s||e<l) return 0;
		if(l<=s&&e<=r) return tree[nod];
		return sol(l,r,s,(s+e)/2,nod*2)+sol(l,r,(s+e)/2+1,e,nod*2+1);
	}

}seg[1515];

ll arr[1515][1515];
string s;
ll dp[1515][1515];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	ll i,j,k,l,m,n,ans=0;
	cin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			cin>>arr[i][j];
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j];
			ans+=dp[i][j];
			seg[i].upt(j,dp[i][j]-dp[i][j-1],1,n,1);
		}
	cout<<ans<<'\n';
	for(i=1;i<=n;i++){
		ll a,b;
		cin>>s>>a>>b;
		ll f1=b;
		ll f2=b;
		ll nf2=1e18;
		if(s[0]=='U'){
			for(j=a;j<=n;j++){
				while(1+seg[j].sol(1,f2,1,n,1)>seg[j-1].sol(1,f2+1,1,n,1)&&f2+1<=n)
					f2++;
				if(j!=a){
					while(seg[j].sol(1,f1-1,1,n,1)>=seg[j-1].sol(1,f1,1,n,1)&&f1<=nf2)
						f1++;
				}
				if(f1>nf2) break;
				seg[j].upt(f1,1,1,n,1);
				if(f2!=n){
					seg[j].upt(f2+1,-1,1,n,1);
				}
				ans+=(f2-f1+1);
				nf2=f2;
				//cout<<i<<' '<<j<<' '<<f1<<' '<<f2<<'\n';
			}	
			arr[j][b]++;
		}
		else{
			for(j=a;j<=n;j++){
				while(seg[j].sol(1,f2,1,n,1)-1>=seg[j-1].sol(1,f2+1,1,n,1)&&f2+1<=n)
					f2++;
				if(j!=a){
					while(seg[j].sol(1,f1-1,1,n,1)>seg[j-1].sol(1,f1,1,n,1)&&f1<=nf2)
						f1++;
				}
				if(f1>nf2) break;
				seg[j].upt(f1,-1,1,n,1);
				if(f2!=n){
					seg[j].upt(f2+1,1,1,n,1);
				}
				ans-=(f2-f1+1);
				nf2=f2;
				//cout<<i<<' '<<j<<' '<<f1<<' '<<f2<<'\n';
			}	
			arr[j][b]--;
		}
		cout<<ans<<'\n';
	}
}