[백준][11048번][DP] 이동하기

이동하기

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

<코드>

#include <stdio.h>
 
int candyMap[1001][1001];
int Dp[1001][1001];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int main(void){
 
    int N, M;
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            scanf("%d", &candyMap[i][j]);
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++){
            int result = 0;
            result =max(Dp[i-1][j-1],max(Dp[i - 1][j], Dp[i][j - 1]));
            Dp[i][j] = result + candyMap[i][j];
        }
 
 
    printf("%d\n", Dp[N][M]);
}

<문제 푼 요령>

1. 이 문제 같은경우는 각각의 최대값을 알기 위해서 비교해야 할 3가지 요소만 잘 비교하면 된다.

2. 비교할 3가지 요소란 Dp[i-1][j] , Dp[i][j-1], Dp[i-1][j-1] 이렇게 3가지를 비교 최대값만 구하면 된다. 

3. 이런식으로 진행하면 DP[N][M]에 정답이나온다.