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

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

( 문제 바로가기 )

[ 문제를 다시 푸는 과정에서 , 이 문제에 대한 풀이글을 다시 포스팅 하였습니다.

  아래의 글을 읽으셔도, 문제를 푸는데에는 무관하지만, 더욱 구체적인 설명을 원하시는 분들께서는

  아래의 링크를 이용해 주시면 감사하겠습니다.

  [ 백준 이동하기(11048) 풀이 새로운 포스팅 ]

]

[ 문제풀이 ]

1) 맵의 (1,1) 에서 (N, M)까지 이동하는데 가져올 수 있는 사탕의 최대갯수를 구해야 하는 문제이다.

   맵에서의 이동은 오른쪽, 아래쪽, 오른쪽 대각선 아래 이렇게 총 3가지 방향으로 나아갈 수 있다.

2) 나는 먼저 맵을 입력받는 2차원 배열 MAP[][]과, 사탕의 수를 저장하는 Candy[][] 이렇게 2개의 2차원 배열을 이용하였다.

   Candy[a][b] = c " (a,b) 정점에서의 사탕의 최대갯수는 c개 입니다. "   를 의미한다.

   그렇다면, 하나의 정점에 저장될 수 있는 사탕의 최대갯수를 구하는 방법에 대해서 구체적으로 알아보자.

   맵이 이렇게 주어져있다고 생각해보자.

   빨강색으로 표시된 (2,2) 정점에서의 최댓값은 무엇이될까 ??

   1 + a, 2 + a, 5 + a의 값들 중 최댓값이 될 것이다. 즉, 5+a의 값이 최댓값이 될 것이다. 왜냐하면 사탕의 갯수는 항상 0보다

   크거나 같기 때문이다.

   즉, (a, b)라는 정점에서 가져올 수 있는 사탕의 최댓값은,

   (a-1, b-1)의 정점에서의 사탕의 갯수 , (a-1, b)의 정점에서의 사탕의 갯수, (a, b-1)의 정점에서의 사탕의 갯수 이 3개의

   값 중 최댓값이 될 것이다.

   위에서 말한 (a-1,b-1), (a-1,b), (a,b-1) 이 3개의 값들도 위의 방식으로 똑같이 사탕의 최대갯수를 구할 수 있다.

  

   위의 설명을 점화식으로 나타내보자면...

   Candy[i][j] = (Cnady[i - 1][j] , Candy[i][j - 1], Cnady[i - 1][j - 1]) 중의 최댓값 + MAP[i][j]가 될 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Candy[MAX][MAX];
 
int Bigger(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++)
        {
            int Result = Bigger(Bigger(Candy[i - 1][j], Candy[i][j - 1]), Candy[i - 1][j - 1]);
            Candy[i][j] = Result + MAP[i][j];
        }
    }
 
    /*for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cout << Candy[i][j] << " ";
        }
        cout << endl;
    }*/
    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;
}