[C++] 백준 11048번 이동하기

 

다이나믹 프로그래밍 문제입니다.

 

0, 0 에서 x, y로 이동 할 때

최대로 얻을 수 있는 값을 찾는 문제입니다.

밑으로, 오른쪽, 대각선으로만 움직일 수 있습니다.

 

for문으로 map을 돌면서

현재 위치의 왼쪽, 위쪽, 대각선 왼쪽위 중 가장 큰 값을 현재 위치에 입력합니다.

이를 코드로 하면 아래와 같습니다.

map[i][j] += max(map[i - 1][j - 1], max(map[i - 1][j], map[i][j - 1]));

 

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

int map[1010][1010];

int main(int argc, char *argv[])
{
   int x, y;
   cin >> x >> y;

   for (int i = 0; i < 1010; ++i) {
      for (int j = 0; j < 1010; ++j) {
         map[i][j] = 0;
      }
   }

   for (int i = 1; i <= x; ++i) {
      for (int j = 1; j <= y; ++j) {
         cin >> map[i][j];
         map[i][j] += max(map[i - 1][j - 1], max(map[i - 1][j], map[i][j - 1]));
      }
   }
   cout << map[x][y];

   return 0;
}