[BOJ]11048번: 이동하기 (c++)

www.acmicpc.net/problem/11048

11048번: 이동하기

 

DP

#include <iostream>
#include <vector>
#include <algorithm>

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>> max_candy(N + 1, vector<int>(M + 1));
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j)
		{
			
			/*
				(i , j) 위치에서의 최대 캔디 개수
				: 현재 위치 캔디 개수 + [현재 위치로 이동 가능한 직전 위치에서의 최대 캔디 개수]
			*/
			cin >> max_candy[i][j];
			max_candy[i][j] += max({ max_candy[i - 1][j], max_candy[i][j - 1], max_candy[i - 1][j - 1] });
		}
	}

	// 출력
	cout << max_candy[N][M];

	return 0;
}

 

배열의 전체 크기를 (N + 1, M + 1) 로 잡으면 편해지는 문제이다.

 

처음엔 maze라는 배열을 따로 만들어서 캔디값을 저장해주었는데,

maze[i][j]는 max_candy[i][j]를 계산할 때 딱 한번 필요했다.

 

그래서 처음부터 주어진 캔디값을 max_candy[i][j]에 저장하고

이전 위치에서의 최대값을 더해주는 방식으로 코드를 수정하였다.