[KTSC 2023 #1] 던전 (BOJ 27508)

던전.pdf

2.19MB

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다.

선발고사 문제 치고는 꽤 쉽다. 하지만 구현이 만만치 않다...

 

예제 속 그림을 보면 중요한 관찰이 눈에 쉽게 보인다.

 

바로 두 경로는 수직 구간 혹은 수평 구간을 정확히 하나 공유한다는 것이다.

이를 바탕으로 수평에 대해서 한 번 풀어주고, 수직에 대해서 같은 방식으로 한 번 풀어준다고 생각하고 한쪽만 고려해보자.

 

수직 구간을 공유한다면 수직 구간의 양 끝점을 기준으로 경로가 정확히 나뉜다. 이를 구간합 배열을 잘 이용하여 합쳐주면 된다.

 

솔직히 좋은 문제는 아니라고 생각한다...

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
using namespace std;
using ll = long long;
const int N = 1003;
int n;
ll v[N][N], p[N][N], x[N][N], y[N][N];
ll a[N][N], b[N][N], c[N][N], d[N][N];

ll solve() {
	rep(j,1,n) rep(i,1,n) {
		p[j][i] = p[j][i-1]+v[i][j];
	}
	fill(a[0],a[N],-1e9), a[0][1] = 0;
	fill(b[0],b[N],-1e9), b[0][n] = 0;
	fill(c[0],c[N],-1e9), c[n+1][1] = 0;
	fill(d[0],d[N],-1e9), d[n+1][n] = 0;
	rep(i,1,n) rep(j,1,n) a[i][j] = max(a[i-1][j],a[i][j-1])+v[i][j];
	rep(i,1,n) per(j,1,n) b[i][j] = max(b[i-1][j],b[i][j+1])+v[i][j];
	per(i,1,n) rep(j,1,n) c[i][j] = max(c[i+1][j],c[i][j-1])+v[i][j];
	per(i,1,n) per(j,1,n) d[i][j] = max(d[i+1][j],d[i][j+1])+v[i][j];
	
	rep(j,1,n) {
		y[j][n+1] = -1e18;
		per(i,1,n) {
			y[j][i] = max({y[j][i+1],
				+p[j][i]+c[i+1][j]+d[i][j+1],
				+p[j][i]+c[i][j-1]+d[i+1][j],
				+p[j][i]+c[i][j-1]+d[i][j+1],
			});
		}
	}
	rep(j,1,n) {
		x[j][0] = -1e18;
		rep(i,1,n) {
			x[j][i] = max({x[j][i-1],
				-p[j][i-1]+a[i-1][j]+b[i][j+1],
				-p[j][i-1]+a[i][j-1]+b[i-1][j],
				-p[j][i-1]+a[i][j-1]+b[i][j+1]
			});
		}
	}
	ll ans = -1e9;
	rep(j,1,n) rep(i,1,n) {
		Mup(ans,y[j][i+1]+x[j][i]);
		Mup(ans,p[j][i]+c[i+1][j]+d[i][j+1]-p[j][i-1]+a[i][j-1]+b[i-1][j]);
		Mup(ans,p[j][i]+c[i][j-1]+d[i+1][j]-p[j][i-1]+a[i-1][j]+b[i][j+1]);
	}
	return ans;
}

int max_item_sum(vector<vector<int>> V) {
	n = siz(V);
	rep(i,1,n) rep(j,1,n) v[i][j] = V[i-1][j-1];
	int ans = solve();
	rep(i,1,n) rep(j,1,n) v[i][j] = V[j-1][i-1];
	Mup(ans, int(solve()));
	return ans;
}