취미로 코딩하기

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

이번에 볼 문제는 백준 11909번 문제인 배열 탈출이다.
문제는 아래 링크를 확인하자.

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

주어진 배열의 각 칸에 도달하는 최소 비용은 (왼쪽 칸에 도달하는 최소비용 + 그 칸에서 지금 칸으로 이동할 때 필요한 비용)과 (위쪽 칸에 도달하는 최소비용 + 그 칸에서 지금 칸으로 이동할 때 필요한 비용) 두 값 중 작은 값이 됨을 관찰하자. 

위의 점화관계를 이용해 dp로 문제를 해결할 수 있다.

이전 행이나 열이 없는 경우 등에 대한 특별한 예외처리가 필요없게끔 아래와 같이 주어진 배열의 위와 왼쪽으로 행을 하나씩 추가해 구현을 편하게 해보자.

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

#include <iostream>
using namespace std;

int N;
int arr[2223][2223];
int dp[2223][2223];

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

	cin >> N;
	
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) cin >> arr[r][c];
	}

	arr[1][0] = arr[0][1] = 1000000007;
	for (int r = 2; r <= N; r++) dp[r][0] = 1000000007;
	for (int c = 2; c <= N; c++) dp[0][c] = 1000000007;

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			int val1 = dp[r - 1][c] + max(arr[r][c] - arr[r - 1][c] + 1, 0);
			int val2 = dp[r][c - 1] + max(arr[r][c] - arr[r][c - 1] + 1, 0);
			dp[r][c] = min(val1, val2);
		}
	}

	cout << dp[N][N];
}