17485번 진우의 달 여행 (Large)

www.acmicpc.net/problem/17485

17485번: 진우의 달 여행 (Large)

 

 

 

 

 

맞은 문제이지만, 이상하게 다른 정답 코드들보다 긴 것 같았다.

(아래는 내 코드이고, 맨 아래 코드가 정답자 분의 코드를 참고하여 다시 구현한 코드이다.)

#include <bits/stdc++.h>

using namespace std;

#define MAX 1010

int m[MAX][MAX], R, C;
int dp[MAX][MAX][3];

int main(void)
{
	cin.tie(0);

	int answer = INT32_MAX;

	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {		
			scanf("%d", &m[i][j]);
			if (i == 0) {
				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = m[i][j];
			}	
		}
	}

	// 0 : ↙, 1 : ↓, 2 : ↘
	for (int i = 1; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (j == 0) {
				dp[i][j][1] += dp[i - 1][j + 1][0] + m[i][j]; // ↙에서 ↓
				dp[i][j][2] += dp[i - 1][j + 1][0] + m[i][j]; // ↙에서 ↘

				dp[i][j][2] = dp[i][j][2] == 0 ? dp[i - 1][j][1] + m[i][j] : min(dp[i][j][2], dp[i - 1][j][1] + m[i][j]); // ↓에서 ↘
			}
			else if (j == C - 1) {
				dp[i][j][1] += dp[i - 1][j - 1][2] + m[i][j]; // ↘에서 ↓
				dp[i][j][0] += dp[i - 1][j][1] + m[i][j]; // ↓에서 ↙

				dp[i][j][0] = dp[i][j][0] == 0 ? dp[i - 1][j - 1][2] + m[i][j] : min(dp[i][j][0], dp[i - 1][j - 1][2] + m[i][j]); // ↘에서 ↙
			}
			else {
				dp[i][j][0] += dp[i - 1][j - 1][2] + m[i][j]; // ↘에서 ↙
				dp[i][j][1] += dp[i - 1][j - 1][2] + m[i][j]; // ↘에서 ↓
				dp[i][j][2] += dp[i - 1][j][1] + m[i][j]; // ↓에서 ↘

				dp[i][j][0] = dp[i][j][0] == 0 ? dp[i - 1][j][1] + m[i][j] : min(dp[i][j][0], dp[i - 1][j][1] + m[i][j]); // ↓에서 ↙
				dp[i][j][1] = dp[i][j][1] == 0 ? dp[i - 1][j + 1][0] + m[i][j] : min(dp[i][j][1], dp[i - 1][j + 1][0] + m[i][j]); // ↙에서 ↓
				dp[i][j][2] = dp[i][j][2] == 0 ? dp[i - 1][j + 1][0] + m[i][j] : min(dp[i][j][2], dp[i - 1][j + 1][0] + m[i][j]); // ↙에서 ↘
			}
		}
	}

	for (int j = 0; j < C; j++) {
		for (int k = 0; k < 3; k++) {
			if (dp[R - 1][j][k] == 0) {
				continue;
			}
			//printf("dp[%d][%d][%d] = %d\n", R - 1, j, k, dp[R - 1][j][k]);
			answer = min(answer, dp[R - 1][j][k]);
		}
	}

	printf("%d\n", answer);

	return 0;
}

 

 

 

 

 

 

아래는 정답자 분들 중에서의 코드를 참고하여 다시 작성해본 코드이다.

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 1010
#define INF 2e9

int m[MAX][MAX], R, C;
int dp[MAX][MAX][3];

int getMinDistance(int r, int c, int d)
{
	if (c < 0 || c >= C) return INF;
	if (d == 0) return min(dp[r][c][1], dp[r][c][2]);
	if (d == 1) return min(dp[r][c][0], dp[r][c][2]);
	return min(dp[r][c][0], dp[r][c][1]);
}

int main(void)
{
	cin.tie(0);

	int answer = INT32_MAX;

	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {		
			scanf("%d", &m[i][j]);
			if (i == 0) {
				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = m[i][j];
			}	
		}
	}

	// 0 : ↙, 1 : ↓, 2 : ↘
	for (int i = 1; i < R; i++) {
		for (int j = 0; j < C; j++) {
			for (int k = 0; k < 3; k++) {
				dp[i][j][k] = getMinDistance(i - 1, j - 1 + k, k) + m[i][j];
			}
		}
	}

	for (int j = 0; j < C; j++) {
		for (int k = 0; k < 3; k++) {
			//printf("dp[%d][%d][%d] = %d\n", R - 1, j, k, dp[R - 1][j][k]);
			answer = min(answer, dp[R - 1][j][k]);
		}
	}

	printf("%d\n", answer);

	return 0;
}