[C++] BOJ #11048 이동하기
Posted on 2022. 02. 27
문제
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.
준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.
준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.
입력
-
첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)
-
둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.
출력
- 첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.
1. 해결방법 및 소스코드
- **동적 프로그래밍(Dynamic Programming)**으로 해결했다.
dp[n][m]을 구하는 것은 내가 해당 (N, M)칸의 입장이 된다고 생각하면 쉽다. 최종적으로 사탕을 많이 얻고싶은데, 다음 세 가지 중에서 최대값을 고르고 싶을 것이다.- 한 칸 왼쪽까지 왔을때의 최대 사탕 개수 + 지금 칸의 사탕 개수
- 한 칸 위쪽까지 왔을때의 최대 사탕 개수 + 지금 칸의 사탕 개수
- 왼쪽대각선 위쪽(↖)까지 왔을때의 최대 사탕 개수 + 지금 칸의 사탕 개수
- dp의 처음 맨 윗줄(0번 행)과 맨 왼쪽 줄(0번 열)은 그저
왼쪽칸(위쪽칸)의 사탕개수 + 현재 칸의 사탕개수만 해주면 최대이므로 그렇게 초기화해놓고dp[1][1]부터 반복문으로 최종결과를 구한다.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N, M;
int maze[1000][1000];
int dp[1000][1000];
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
scanf("%d", &maze[i][j]);
}
}
dp[0][0] = maze[0][0];
for (int i = 1; i < M; i++)
{
dp[0][i] = maze[0][i] + dp[0][i - 1];
}
for (int i = 1; i < N; i++)
{
dp[i][0] = maze[i][0] + dp[i - 1][0];
}
for (int i = 1; i < N; i++)
{
for (int j = 1; j < M; j++)
{
dp[i][j] = maze[i][j] + max(max(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);
}
}
printf("%d\n", dp[N - 1][M - 1]);
}