[ACM-ICPC][BOJ] 10251 - Driving License

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2014 예선전 B번 문제인 Driving License 풀이를 해보겠습니다.

4차원 배열을 활용한 dp 문제로 어떻게 이런 아이디어를 내는지.. 정말 출제자나 푸신 분들이나 대단하네요...

저는 도저히 아이디어가 안 떠올라서 https://blog.encrypted.gg/86 님의 설명을 참고해서 문제를 풀었습니다.

---

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

불러오는 중입니다...

[알고리즘풀이]

이 문제의 핵심 힌트는 오른쪽 또는 아래로만 이동할 수 있고, 최소 이동 횟수는 오직 방향 전환(turn)에 의존하는 점입니다.

 

DP[i][j][k][d]  : (0,0) 부터 (i,j) 까지 k번 turn하고 d( 0 : 왼->오, 1 : 위->아래) 방향으로 왔을 때 최소 연료양

row[i][j] : i 번째 row 에서 j ~ j + 1 column까지 이동하는데 필요한 연료.

column[i][j] : i ~ i + 1 row까지  j 번째 column에서 이동하는데 필요한 연료.

 

다음과 같이배열을 정의한다. 그러면, 다음과 같은 방정식이 성립한다.

DP[i][j][k][0] = min(dp[i][j - 1][k][0] + row[i][j - 1], dp[i][j - 1][k - 1][1] + row[i][j - 1])

DP[i][j][k][1] = min(dp[i - 1][j][k][1] + column[i - 1][j], dp[i - 1][j][k - 1][0] + column[i - 1][j])

 

따라서 DP배열을 다 채우고나면 목표지점인 (N,M)에 대해 K 를 작은 값부터 순회하며, 기준 연료양보다 낮은 값을 발견하면 거리를 출력하면 된다.

 

#주의#

DP배열을 미리 큰 값으로 초기화하지 않으면, 기준 연료양보다 낮은 값이 DP[N][M][0][0] 에서 발견되므로 항상 큰 값들로 초기화해줘야 된다.

#include<iostream>
#include<algorithm>

using namespace std;

int dp[101][101][200][2];
int row[100][100];
int column[100][100];

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

	int t;
	cin >> t;

	while (t--) {
		int r, c, l, g;
		cin >> r >> c >> l >> g;
		// row[i][j] 는 i 줄 j ~ j + 1까지의 연료.
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c - 1; j++)
				cin >> row[i][j];
		}
		// colum[i][j]는 i ~ i + 1 줄 j 의 연료.
		for (int i = 0; i < r - 1; i++)
			for (int j = 0; j < c; j++)
				cin >> column[i][j];

		int maxturn = 2 * max(r, c);
		// dp를 초기화시키자.
		for (int i = 0; i < r; i++)
			for (int j = 0; j < c; j++)
				for (int k = 0; k <= maxturn; k++)
					for (int l = 0; l < 2; l++)
						dp[i][j][k][l] = 99999999;
		dp[0][0][0][0] = 0, dp[0][0][0][1] = 0;
		// dp를 먼저 채워보자.
		for (int j = 1; j < c; j++)
			dp[0][j][0][0] = dp[0][j - 1][0][0] + row[0][j - 1];
		for (int i = 1; i < r; i++)
			dp[i][0][0][1] = dp[i - 1][0][0][1] + column[i - 1][0];
		// 나머지는 점화식을 활용해 채워보자.
		for (int i = 1; i < r; i++)
			for (int j = 1; j < c; j++) {
				maxturn = 2 * max(i, j);
				for (int k = 1; k <= maxturn; k++) {
					dp[i][j][k][0] = min(dp[i][j - 1][k][0] + row[i][j - 1], dp[i][j - 1][k - 1][1] + row[i][j - 1]);
					dp[i][j][k][1] = min(dp[i - 1][j][k][1] + column[i - 1][j], dp[i - 1][j][k - 1][0] + column[i - 1][j]);
				}
			}
		// 답을 도출해보자.
		bool flag = false;
		maxturn = 2 * max(r, c);
		for (int k = 0; k <= maxturn; k++) {
			if (dp[r - 1][c - 1][k][0] <= g || dp[r - 1][c - 1][k][1] <= g) {
				cout << l * (r - 1 + c - 1) + k << '\n';
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << "-1\n";
		}

	}
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.