[백준] 알고리즘 11048번 - 이동하기문제

문제

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

11048번: 이동하기

소스코드

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int n, m;
int arr[1001][1001],dp[1001][1001];;

int main() {
	ios_base::sync_with_stdio(false), cin.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++) {
			dp[i][j] = max({ dp[i - 1][j],dp[i][j - 1],dp[i - 1][j - 1] })+arr[i][j];
		}
	}
	cout << dp[n][m];
}

 

해설

(r,c) -> (r+1,c) (r,c+1), (r+1,c+1) 로 이동하여 사탕을 가져갈 수 있는 최대값을 물어보는 문제이다.

dp[r][c] 의 의미를 생각해봐야한다. (r,c)에 왔을 때 사탕을 가질 수 있는 최대값을 저장한다고 정의를 해봅시다.

그렇다면 그 다음이동을 할 수 있는건 저 위에 3가지 방법인데, 반대로 (r,c)에서 그 이전의 값 즉 r,c가 되기 전의 상황에도 사탕을 가질 수 있는 최대값이 저장되어 있을 것이다.

그렇다면 점화식을 dp[r][c] = max(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + arr[r][c] 로 정의 할 수 있다.