[백준 DP] 11048번 - 이동하기

11048번 - 이동하기 

 

<문제>

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

11048번: 이동하기

 

<문제 풀기>

문제를 이해하고 가장 먼저 떠오른 방법은 역추적이다. 

알고리즘 학부 수업시간에서 최단경로 문제를 풀 때 역추적으로 해결한 기억이 있어 추적의 시작점을 dp [N][M]으로 설정하였다. 실행 결과는 동일하지만 제출하니 틀렸다고 한다....

역추적으로 문제 풀이를 시작한 만큼 해결하고 싶었는데 얼떨결에 dp [1][1]부터 시작한 추적도 답과 동일한 결과가 나왔다. 

점화식은 간단하다. arr[i-1][j], arr[i][j-1], arr[i-1][j-1]의 값을 비교하여 가장 큰 값을 누적하여 출력 값을 구해주면 된다. 

점화식: arr[i][j] += max({arr [i - 1][j], arr[i][j - 1], arr[i - 1][j - 1]})

(아직 역추적 문제 해결 못 함.)

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int arr[1001][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			arr[i][j] += max({ arr[i - 1][j], arr[i][j - 1], arr[i - 1][j - 1] });
		}
	}

	cout << arr[N][M] << '\n';
	return 0;
}

 

-> 역추적 

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int arr[1001][1001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = N; i >= 1; i--) {
		for (int j = M; j >= 1; j--) {
			arr[i][j] += max({ arr[i + 1][j], arr[i][j + 1], arr[i + 1][j + 1] });
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}

	cout << arr[1][1] << '\n';
	return 0;
}

 

<결과>

 

 

2022.12.28