[BOJ] 11048번 | 이동하기 (C++)

🔗문제 보러가기

11048번: 이동하기

 

🧑🏻‍💻풀이 과정

DP(Dynamic Programming)로 풀 수 있습니다. 알고리즘은 다음과 같습니다.

 

1. (0, 0)부터 시작하여 0행과 0열에 대해 누적합을 저장해 나가며, 초기화를 해줍니다.

예제 입력 1번을 예로 들면 다음과 같이 합니다.

// 원본 입력 데이터
1 2 3 4
0 0 0 5
9 8 7 6

// 누적합 적용 후
1        3(2+1)  6(3+3)  10(6+4)
1 (0+1)  0       0       5
10(9+1)  8       7       6

 

2. 1행 1열부터 열방향으로 탐색하며, {위쪽, 왼쪽, 왼쪽 위 대각선} 중에 (제일 큰 값 + 현재 값)을 더해 저장합니다.

문제에서 이동 방향이 {아래쪽, 오른쪽, 오른쪽 아래 대각선} 이렇게 세 개였습니다. 반대로 생각하면, {위쪽, 왼쪽, 왼쪽 위 대각선}에는 각각 이때까지의 누적합이 존재한단 의미이므로, 이중에 가장 큰 누적합과 현재 값을 더해 현재 위치에 저장하는 식으로 반복하면 됩니다.

1   3                      6                      10
1   3{0 + max(3, 1, 1)}    6{0 + max(6, 3, 3)}    15{5 + max(10, 6, 6)}
10  18{8 + max(3, 10, 1)}  25{7 + max(6, 18, 3)}  31{6 + max(15, 25, 6})

이런 식으로 찾아가면, [N-1][M-1]에 최댓값이 존재하게 됩니다.

 

✏️소스 코드 및 결과

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

int FindMaxCandyCount(vector<vector<int>>& maze, int N, int M)
{
	// 0행 누적합 적용
	for (int row = 1; row < N; row++)
		maze[row][0] += maze[row - 1][0];

	// 0열 누적합 적용
	for (int col = 1; col < M; col++)
		maze[0][col] += maze[0][col - 1];

	// {위쪽, 왼쪽, 대각선 왼쪽 위} 중에 제일 큰 수와 현재 수를 더해서 저장
	for (int row = 1; row < N; row++)
		for (int col = 1; col < M; col++)
			maze[row][col] += max({ maze[row - 1][col], maze[row][col - 1], maze[row - 1][col - 1] });
	return maze[N - 1][M - 1];
}

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

	int N, M;
	cin >> N >> M;
	
	vector<vector<int>> maze(N, vector<int>(M));
	for (int r = 0; r < N; r++)
		for (int c = 0; c < M; c++)
			cin >> maze[r][c];

	int answer = FindMaxCandyCount(maze, N, M);
	cout << answer;
	return 0;
}