이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 19 번째 글 입니다.
목차
실버1 : 동적 계획법 문제이다.
생각
DFS나 BFS로는 depth가 깊어져 시간초과가 난다. 이 문제는 동적계획법으로 풀어야 한다. 그저 최대 사탕의 개수만 출력하면 되기 때문이다.
정의
이 문제는 위치에 따라 개수가 결정되므로 dp의 인자를 좌표의 위치로 잡는 것이 수월하다.
dp[y][x] = (y,x)위치에서 가질 수 있는 사탕 개수의 최댓값
점화식
이 정의에 부합하는 점화식은 어떤식으로 짤 수 있을까? 점화식은 임의의 좌표 위치에서 이 좌표가 만들어지기 위해 어떤 좌표와의 연관성이 있는지를 확인하면 된다. 문제에서 특정 위치에서 갈 수 있는 방향은 우, 좌, 대각이다. 그렇다면 특정 위치에서의 사탕의 최댓값은 좌, 우, 10시방향 대각선 세 방향의 값으로 부터 도출될 수 있다.
dp[y][x] = max(dp[y-1][x], dp[y][x-1], dp[y-1][x-1]) + input[y][x]
주의할 점
(1, 1)에서 시작하므로 (1, 1), (1행, 1), (1, 1열)의 위치에서는 3방향에서 업데이트를 할 수 없다. 이 점을 고려하여 분기를 만들어 코드를 짜는 것이 좋다.
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N, M;
int map[1001][1001];
int dp[1001][1001];
int main(){
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> map[i][j];
if (i == 1 && j == 1) dp[i][j] = map[i][j];
}
}
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= M; x++) {
if (y == 1 && x == 1) {
continue;
} else if (y == 1){
dp[y][x] = max(dp[y][x], dp[y][x-1]);
} else if (x == 1){
dp[y][x] = max(dp[y][x], dp[y-1][x]);
} else {
dp[y][x] = max(dp[y][x], dp[y-1][x]);
dp[y][x] = max(dp[y][x], dp[y][x-1]);
dp[y][x] = max(dp[y][x], dp[y-1][x-1]);
}
dp[y][x] += map[y][x];
}
}
cout << dp[N][M] << '\n';
}