BOJ 14869 - 요리 강좌

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

문제 태그

DP, deque, Segment Tree

문제 풀이 (의식의 흐름)

 기본적으로 난이도가 있는문제이다. 일단 이 문제를 보자마자 이 문제가 DP라는 사실을 깨닫지 못했다면, 앞으로의 관찰은 거의 불가능한 난이도라고 생각해도 좋다. 그럼 DP 테이블을 정의해보려고 해보자.

 일단 몇번째 강좌인지가 중요할 것이고, 어느 학원에서 듣는지가 중요할 것이다. 그렇게 $DP[i][j]$를 i번째 강좌를 j번 학원에서 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 이러면 문제는 문제의 조건인, 한 학원에서 s~e 개를 연속해서 듣기를 만족할 수 없다. 그렇다고 $DP[i][j][k]$를 설정해서 k를 j번째 학원에서 현재 k번째 연속 수강을 하고 있을 때라고 설정하면 벌써 $O(N^3)$이 나오게 된다. 이때 쓰는 방법이 "마지막"
DP[i][j]= i번째 강좌를 j번 학원에서, 연속한 마지막으로 수강할 때, 이때까지의 비용의 최솟값이라고 설정하자. 즉 i+1번째 강좌는 j가 아닌 다른 학원에서 수강할 것이다.

 DP table의 정의가 끝났으니 DP식을 세워야 한다. 문제의 조건에서 x의 전 학원이 될 수 없는 학원을 not[x]라고 하자. 그러면 $i-e \leq {i}'\leq i-s$ 인 ${i}'$과 ${j}' \neq j, {j}'\neq not[j]$ 인  ${j}'$ 에 대하여 아래와 같은 식이 나오게 된다.
\[DP[i][j]=\underset{{i}',{j}'}{min}(DP[{i}'][{j}']+T+\sum_{k={i}'+1}^{i}arr[k][j])\]
이 식에 의해서 한 DP table을 채우기 위해서 드는 시간복잡도는 $O(N^3)$이다.${i}'$와 ${j}'$ 으로 가능한 쌍의 갯수는 $O(N^2)$ 이고, 시그마를 구하는데 $O(N)$이 들기 때문이다. 그래서 총 시간복잡도는 $O(N^5)$이고, 우리는 여러가지 관찰과 테크닉을 활용하여 시간복잡도를 줄여가야 한다.

1. 가능한 ${j}'$에 대해서 생각해보면 안되는 경우는 두가지이다. 하지만, 나머지 모두를 봐야할까? 같은 i에 대해서 더 좋은 j는 정해져 있다. 다시말해 i번째날 j학원에서 끝나고 이번 학원으로 넘어올건데, 가능한 j학원들 중 가장 좋은 학원은 이미 정해져있다는 것이다. DP의 핵심은 작은 문제의 최선의 답이 더 큰문제의 최선의 답으로 이어지는 것이다. 똑같이 우리는 당연하게도 가장 좋은 경우에서 다음상황으로 넘어갈 것이다. 이때 불가능한 2가지 경우가 있으므로 각 날짜별로 최소의 경우 3가지만 확인하자. 모든 경우에 대해서 이 3가지만 확인해도 이들 중 최솟값이 있다는 것을 생각해낼 수 있다. 따라서 우리는 ${j}'$의 경우의 수를 3가지로 줄였고 시간복잡도 $O(N)$을 날릴 수 있었다. 
 여담으로 개인적으로 여기까지는 굉장히 쉽게 생각했던 것 같다. 최근에 경우의 수 관련해서 많이 다뤄봐서 더 좋은 경우, 없앨 수 있는 경우들을 보는 능력이 많이 상승했다.

2. https://stonejjun.tistory.com/96 를 보고 오자. 이 문제를 풀다가 쓴 글이다. 항상 DP에서 구간 합이 나오면 prefix sum을 생각하라. 공식같은 느낌이지만 확답을 드리기는 어려울 것 같고, 다만 한 번쯤 생각해봐야 한다는 점은 강력하게 주장할 수 있다. 아무튼 $pre[i][j]=pre[i-1][j]+arr[i][j]$ 즉, i일차까지 j학원의 비용의 합으로 정의를 해보자. 그러면 위에서 적었던 식이 아래와 같이 바뀌게 된다.
$DP[i][j]=\underset{{i}',{j}'}{min}(DP[{i}'][{j}']+pre[i][j]-pre[{i}'][j]+T])$ 이로써 또 $O(N)$의 시간 복잡도를 절약할 수 있었다. 

3. 위의 식에서 분리를 해보자. $DP[i'][j']-pre[i'][j]$ 부분과 $ pre[i][j]+T $ 부분으로 말이다. 앞의 부분은 i'에 관한 식이다. 즉 i-e~i-s 시점에서 미리 구해놓을 수 있다. 이때 구해놓은 값은 i'+s~i'+e에서 계속 사용하게 된다. 즉 식을 N번 따로 구할 필요 없이 한 번 설정해 놓고 나중에 i만 바꿔가면서 $pre[i][j]+T$를 더해주면 된다는 것이다. 
j와 i에 대해서 $DP[i'][j']-pre[i'][j]$ 최솟값은 정해져 있다. 이를 j번째 세그먼트 트리의 i'번째 위치에 저장을 하자. 나중에 i-e~i-s의 구간 최솟값을 꺼내서 $pre[i][j]+T$ 를 더해주면 $O(N)$을 $O(lgN)$으로 줄였으므로 총 시간복잡도 $O(N^2lgN)$에 문제를 해결할 수 있게 되었다. 
 이때 세그먼트 트리 대신에 priority_queue를 쓰거나 sliding window technique로 deque을 사용하여도 문제를 해결할 수 있다. 특히 deque을 사용하면 전체 시간복잡도 $O(N^2)$으로 문제를 해결할 수 있고 더 안전하다.

여담

일단 식을 너무 안쓰고 머리로 풀 수 있을 것이라고 생각해서 3번을 생각하는데 꽤 시간이 걸렸다. 그래도 한번 식을 적고 나니까 CHT를 많이 해봐서 그런지 어떤식으로 풀어나갈지 바로 생각이 들었다. 그런데 이 문제의 입력순서가 i가 학원 j가 강좌 같은 느낌이라서 전체적으로 i와 j가 엄청 꼬이게 된다. 처음에 짠 코드에서 우선순위큐->세그트리->deque를 모두 해봤지만 20틀을 박고 망했다. 결국 처음부터 코드를 다시 짜서 바로 맞았다. koi DP라서 그런지 구현에서 뇌절할 부분이 많고, 사실 그와 별개로 내가 너무 구현을 못했나 보다. 처음 짠 코드는 왜 틀렸는지 아직도 모른다. 

코드

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

#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back

ll no[10101];
ll arr[3030][3030];
ll pre[3030][3030]; //i번째 학원 j번째 수강

struct poi{
	ll idx,val;
};

bool sf(poi a,poi b){
	return a.val<b.val;
}

deque<pii> dq[3030];
ll dp[3030][3030];
poi spe[3030][4];

ll sol(ll d,ll x){
	if(no[x]!=spe[d][0].idx&&x!=spe[d][0].idx) return spe[d][0].val;
	if(no[x]!=spe[d][1].idx&&x!=spe[d][1].idx) return spe[d][1].val;
	if(no[x]!=spe[d][2].idx&&x!=spe[d][2].idx) return spe[d][2].val;
}

void put(ll d,ll x,ll v){
	spe[d][3].val=v;
	spe[d][3].idx=x;
	sort(spe[d],spe[d]+4,sf);
	return;
}

void dbp(ll d,ll x,ll v){
	while(!dq[x].empty()&&dq[x].back().ss>v)dq[x].pop_back();
	dq[x].push_back({d,v});
	return;
}

int main(){
	ll i,j,k,l,m,n,s,e,t;
	cin>>m>>n>>s>>e>>t;
	for(j=1;j<=m;j++)
		for(i=1;i<=n;i++){
			cin>>arr[i][j];
			pre[i][j]=pre[i-1][j]+arr[i][j];
		}

	for(j=1;j<=m;j++)
		cin>>no[j];

	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			dp[i][j]=1e18;
		for(j=0;j<4;j++)
			spe[i][j].val=1e18;

	}
	for(j=1;j<=m;j++)
		dq[j].push_back({0,-t});

	for(i=s;i<=n;i++){
		for(j=1;j<=m;j++){
			if(i==n){
				for(k=i-s+1;k<n;k++){
					dbp(k,j,sol(k,j)-pre[k][j]);
				}
			}
			while(dq[j].front().ff<i-e) dq[j].pop_front();
			dp[i][j]=dq[j].front().ss+pre[i][j]+t;
			put(i,j,dp[i][j]);
		}
		for(j=1;j<=m;j++){
			ll k=i-s+1;
			dbp(k,j,sol(k,j)-pre[k][j]);
		}
	}

	ll ans=1e18;
	for(j=1;j<=m;j++)
		ans=min(ans,dp[n][j]);

	cout<<ans;


}