[ 백준 11048 ] 이동하기 (C++)

백준의 이동하기(11048) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

하나의 좌표에서는 총 3가지 방향으로 나아갈 수가 있다.

오른쪽 / 아래쪽 / 대각선 이렇게 총 3가지 방향으로 나아갈 수가 있다.

(x , y)라는 좌표가 있을 때, (x + 1 , y), (x , y + 1), (x + 1 , y + 1) 로 갈 수 있다는 것인데, 그럼 역으로 생각해보자.

(x , y)로 오기 위해서는 어떤어떤 좌표들에서 올 수 있을지를 생각해보자.

(x , y)로 올 수 있는 좌표로는, 아마 (x - 1 , y) , (x , y - 1) , (x - 1 , y - 1) 이렇게 3개의 좌표가 있을 것이다.

그런데 우리는 ! 최대한 많은 사탕을 가져와야 한다.

그럼, (x , y)에서는 (x - 1, y)에서도, (x , y - 1)에서도, (x - 1, y - 1)에서도 올 수가 있는데, 이 때 최대한 많은 사탕을 가져오기 위해서는 어느 좌표를 선택해 주어야 할까 ??

바로, 위에서 말한 3가지 좌표중에서, "사탕을 가장 많이 가지고 있는 좌표"를 선택해주면 된다.

그럼 위의 내용을 하나의 수식을 이용해서 나타내보자.

F[A][B] = C 인데, 이 수식의 의미는 "(A , B)까지 왔을 때, 가져올 수 있는 사탕의 최대 갯수는 C개입니다."를 의미한다.

그럼 F[x][y] 의 값은 얼마일까 ???

F[x][y] = Max(F[x - 1][y] , F[x][y - 1], F[x - 1][y - 1]) + MAP[x][y] 가 되는 것이다.

뒤에 '+ MAP[x][y]' 의 의미는, (x , y)까지 오게되면, 해당 좌표에 있는 사탕의 갯수도 가져갈 수 있으므로 기존의 사탕의 갯수에 현재 좌표에 있는 사탕의 갯수를 더해주는 것이다.

이를 점화식으로 사용해서, 모든 좌표들에 대해서 가져올 수 있는 사탕의 최대갯수를 구해주면 된다.

최종적인 정답은 F[N][M]에 저장되어 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Candy[MAX][MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            Candy[i][j] = Max(Max(Candy[i - 1][j], Candy[i][j - 1]), Candy[i - 1][j - 1]) + MAP[i][j];
        }
    }
    cout << Candy[N][M] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}