[BOJ/백준 11048][C++] 이동하기

문제

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

 

문제 내용

(1,1)에서 (n,m)으로 가면서, 사탕을 최대한 많이 얻을 수 있도록 하면 된다.

이동할 수 있는 방향은 왼쪽/아래쪽/왼쪽아래 대각선 총 3가지이다.

 

문제 풀이

dp를 사용하여 문제를 풀면 된다.

arr배열에 각 위치의 사탕개수를 입력받고, for 반복문을 통해 dp배열을 채워나가면 된다.

어떤 특정한 위치는, 오른쪽/위쪽/오른쪽 위 대각선 방향으로부터 올 수 있다.

따라서 내가 구하려는 dp[i][j]의 값은 오른쪽(dp[i-1][j]) / 위쪽(dp[i][j-1]) / 오른쪽 위(dp[i-1][j-1])의 값 중에 가장 큰 값과 그 위치에 있는 사탕의 개수(arr[i][j])을 더하여 구할 수 있다.

 

 

코드

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


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

	//입력
	int n, m;
	cin >> n >> m;
	vector<vector<int>>arr(n + 1, vector<int>(m + 1, 0));
	vector<vector<int>>dp(n + 1, vector<int>(m + 1, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = arr[i][j];
		}
	}

	//문제 해결
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = arr[i][j] + max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));
		}
	}
	
    	//결과 출력
	cout << dp[n][m] << '\n';
}

 

문제 코드 설명

1) 입력

vector<vector<int>>arr(n + 1, vector<int>(m + 1, 0));

이 코드의 뜻은, 크기가 (n+1)*(m+1)인 이차원 배열을 만들고, 모든 원소의 값을 0으로 초기화한다는 의미이다.