Boj 255713) 괴도 인하

문제

백준 25713

설명

감시카메라의 영역에 들어가는 방법은 한정되어 있다. 그러므로 감시카메라 영역에 들어가는 Edge 에 Weight 를 부여한다.

Grid 형태이고 Right/Left 방향 뿐이므로 Grid 와 같은 배열을 두개 만들어서 각각 Right/Left 방향 간선이라고 두먼 편하게 계산할 수 있다.

그러면 간단한 DP 문제가 된다.

시간 복잡도

O(\(\mathrm{N} \mathrm{M}\))

코드

int dp[1002][1002], dx[1002][1002], dy[1002][1002];

int main()
{
	int n, m, k; cin >> n >> m >> k;;
	for (int i = 0; i < k; i++)
	{
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		for (int j = x1; j <= x2; j++) dy[y1][j] += 1;
		for (int j = y1; j <= y2; j++) dx[j][x1] += 1;
	}
	
	// 편의상 시작위치와 연결되지 않는 가장자리는 최댓값 부여
	for (int i = 2; i <= n; i++) dp[i][0] = 1e9;
	for (int i = 2; i <= m; i++) dp[0][i] = 1e9;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] += min(dp[i - 1][j]+dy[i][j], dp[i][j - 1]+dx[i][j]);

	cout << dp[n][m];
}