BOJ - 이동하기(11048)

실버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';
}

Reference

• 백준(11048번) - 이동하기