[백준 / BOJ / SILVER 1] 11048 번 : 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

 

문제 접근 방법

• 원점으로부터 이동 할 수 있는 위치를 파악한다(우측, 우측 대각선 아래, 아래) 3가지 방향이다.
• 이동되는 점의 기준으로 보면 자신으로 올 수 있는 곳은 좌측, 좌측 대각선 위, 위 이렇게 3가지 방향이다.
• 가져올 수 있는 최대 사탕의 갯수를 구해야 하기 때문에 자신에게 올 수 있는 방향의 사탕 갯수를 비교하여 그중 가장 큰 값과 현재 자신 위치의 사탕 갯수를 더하면 최댓값이 된다.

아래는 코드입니다.

#include <iostream>
 
using namespace std;
 
int candyMap[1001][1001];
int totalCandy[1001][1001];
 
int MaxCheck(int a, int b, int c)                                // 3개중 가장 큰 것을 리턴하는 함수
{
    return a > b ? (a > c ? a : c ) : b > c ? b : c;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int N, M;
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> candyMap[i][j];
        }
    }
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            totalCandy[i][j] = MaxCheck(totalCandy[i - 1][j], totalCandy[i - 1][j - 1], totalCandy[i][j - 1]) + candyMap[i][j];            // 올 수 있는 방향 3가지로부터 비교하여 최대값 + 도달 위치에 있는 사탕 갯수를 더함
        }
    }
 
    cout << totalCandy[N][M] << "\n";
 
    return 0;
}