백준 11048번 이동하기

문제 링크입니다: https://www.acmicpc.net/problem/11048

동 서 남 북을 고려하지 않고 동, 남, 남동 방향만 고려하면 됬기 때문에 쉽게 풀 수 있던 문제였습니다.

/*

준규는 N×M 크기의 미로에 갇혀있다.

미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다.

미로의 가장 왼쪽 윗 방은(1, 1)이고, 가장 오른쪽 아랫 방은(N, M)이다.

준규는 현재(1, 1)에 있고, (N, M)으로 이동하려고 한다.준규가(r, c)에 있으면, (r + 1, c), (r, c + 1), (r + 1, c + 1)로 이동할 수 있고,

각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다.또, 미로 밖으로 나갈 수는 없다.

준규가(N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최대값을 구하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

int N, M; //세로, 가로

int maze[1001][1001]; //N, M<=1000

int cache[1001][1001]; //N, M<=1000

 

int maxCandy(int y, int x)

{

        if (y < 0 || y>N || x < 0 || x>M)

               return 0; //범위 초과

        int &result = cache[y][x];

        if (result != -1)

               return result;

        result = maze[y][x];

        //(y+1, x)로 갔을 경우, (y, x+1)로 갔을 경우 그리고 (y+1, x+1)로 갔을 경우 중 최대 값 반환

        return result += max(maxCandy(y + 1, x), max(maxCandy(y, x + 1), maxCandy(y + 1, x + 1)));

}

 

int main(void)

{

        cin >> N >> M;

        for (int i = 1; i <= N; i++)

               for (int j = 1; j <= M; j++)

                       cin >> maze[i][j];

 

        memset(cache, -1, sizeof(cache));

        cout << maxCandy(1, 1) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~