문제: boj 11048

풀이

  • maze: 미로안의 사탕수 배열, candy: 그 칸을 지났을 때 최대 사탕수
  • candy[i][j] = max(candy[i][j-1]+maze[i][j], candy[i-1][j] + maze[i][j])의 점화식을 갖게 된다.
  • 모든 배열을 한번씩 지나면서 점화식을 계산해 배열 candy를 채운다.

C++

#include <iostream>
#include <cstdio>
using namespace std;

int N, M;
int maze[1001][1001];
int candy[1001][1001];

void dp(){
    for(int i(0);i < N; i++){
        for(int j(0); j < M ;j++){
            if(i == 0 && j >0){
                candy[i][j] = candy[i][j-1] + maze[i][j];
            }
            else if(i > 0) {
                candy[i][j] = max(candy[i][j-1]+maze[i][j], candy[i-1][j] + maze[i][j]);
            }
        }
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int n(0); n < N; n++){
        for (int m(0); m < M; m++){
            cin >> maze[n][m];
        }
    }
    candy[0][0] = maze[0][0];
    dp();
    cout << candy[N-1][M-1];
    fclose(stdin);

    return 0;
}