개요

백준 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)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

접근방식

dp 방식

1. dp 이차원 배열을 선언해줬다. dp[i][j]가 들고 있는 값은
   좌표(i,j)까지 들고 올수 있는 사탕의 최대값이다.

2. 세 갈래로 뻗어가는 식이라 재귀함수를 통해 풀이를 하는게 편할 것 같았다.

3. 사탕을 더해가며 뻗어나가는 식이라 n,m을 처음 함수에 넣고,
   n,m을 0이 될때까지 분해한 후, 다시 합치는 방식을 사용했다.

   int Dp(int r, int c) {
      if (r < 0 || c < 0) return 0;
      int* ret = &dp[r][c];
      if (*ret != -1) return *ret;
   
      *ret = max(Dp(r - 1, c), max(Dp(r, c - 1), Dp(r - 1, c - 1))) + candy[r][c];
      return *ret;
   }

4. 아래 코드처럼 당장 Dp(r,c)함수들만 비교해서 제일 큰값을 더해버리면

    *ret = max(Dp(r - 1, c), max(Dp(r, c - 1), Dp(r - 1, c - 1))) ;

   dp값에는 아무 값도 안 들어있기때문에 답이 안나온다.
   candy[r][c]값을 더해주는 부분을 추가해야한다.

   따라서 각 단계에서는 이전 DP값에 현재 단계의 candy값을 더해주는식으로 구현했다.
   이런식이면 r과 c가 0일때면 Dp(-1,0), Dp(-1,-1), Dp(0,-1) 전부 0을 반환하기때문에
   원하는대로 저장이 된다.

      *ret = max(Dp(r - 1, c), max(Dp(r, c - 1), Dp(r - 1, c - 1))) + candy[r][c];

전체 코드

#include<iostream>
using namespace std;
int N, M, tmpNum;
int dp[1002][1002];
int candy[1002][1002];
int Dp(int r, int c) {
    if (r < 0 || c < 0) return 0;
    int* ret = &dp[r][c];
    if (*ret != -1) return *ret;

    *ret = max(Dp(r - 1, c), max(Dp(r, c - 1), Dp(r - 1, c - 1))) + candy[r][c];
    return *ret;
}

int main() {
    fill(&dp[0][0], &dp[1000][1001], -1);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> tmpNum;
            candy[i][j] = tmpNum;
        }
    }
    cout << Dp(N-1,M-1);
}