취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25713번 문제인 괴도 인하이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25713 

게임기에 도달할 때까지의 괴도 인하의 움직임은 오른쪽 움직임과 아래쪽 움직임으로 구성되어있다는 점을 눈여겨보자.

한 경로가 특정 카메라가 비추는 경로를 지나간다면, 해당 경로는 카메라가 비추는 범위의 가장 위쪽 칸 또는 가장 왼쪽 칸을 무조건 지나게 된다는 점을 확인하자. 이 점과 (r,c)까지 도달하는 모든 경로는 (r-1,c)를 거쳐왔거나 (r,c-1)을 거쳐올 수밖에 없다는 점을 이용하면 점화식을 간단히 세워 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C, K;
int dp[1001][1001];
int rowmove[1001][1001], colmove[1001][1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C >> K;
	while (K--) {
		int r1, c1, r2, c2; cin >> r1 >> c1 >> r2 >> c2;
		for (int r = r1; r <= r2; r++) {
			rowmove[r][c1]++;
		}
		for (int c = c1; c <= c2; c++) {
			colmove[r1][c]++;
		}
	}

	dp[1][1] = colmove[1][1];
	for (int r = 2; r <= R; r++) dp[r][1] = dp[r - 1][1] + colmove[r][1];
	for (int c = 2; c <= C; c++) dp[1][c] = dp[1][c - 1] + rowmove[1][c];
	for (int r = 2; r <= R; r++) {
		for (int c = 2; c <= C; c++) {
			dp[r][c] = min(dp[r - 1][c] + colmove[r][c], dp[r][c - 1] + rowmove[r][c]);
		}
	}

	cout << dp[R][C];
}