[C++][백준] - 이동하기 (11048번)

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

11048번: 이동하기

🔔 문제 : 

(1 <= N, M <= 1,000)인 N*M의 크기의 미로가 있습니다.

 

가장 왼쪽 윗 방은 (1,1) 이고 가장 오른쪽 아랫 방은 (N, M)입니다 

 

각 방에는 사탕이 개수만큼 놓여져 있습니다.

 

이동은 (r+1, c) (r, c+1)k, (r+1, c+1)로만 이동 할 수 있습니다.

 

(1,1)에서 (N,M)까지 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하면 됩니다.

---

🔔 Kick Point :

F(r,c)의 값은 = Max( { F(r-1, c), F(r-1,c-1) , F(r, c-1) } + (r,c)의 사탕값 으로 DP , 세분화 할 수 있습니다. 따라서

 

(1,1) 방부터 차례대로 Bottom-up 방식대로 사탕의 최댓값을 구하였습니다.

 

---

🔔 Code :

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

int main() {
	int n, m; cin >> n >> m;
	int dest = n * m;
	vector<int> dp(dest);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int tmp; cin >> tmp;
			int idx = i * m + j;
			
			if (i == 0 && j == 0) dp[idx] = tmp;
			else if (i == 0) dp[idx] = dp[idx - 1] + tmp;
			else if (j == 0) dp[idx] = dp[idx - m] + tmp;
			else dp[idx] = max({ dp[idx - m], dp[idx - 1], dp[idx - 1 - m] }) + tmp;
		}
	}
	
	cout << dp[dest -1];
}

---