이동하기_백준11048

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

11048번: 이동하기

이동할 수 있는 경우의 수는 x , y 좌표 둘다 +1 또는 둘중 하나만 +1인 경우이다

각 좌표에 도착했을때 3가지 경우를 비교하여 가장 큰 수를 지정해 주면 최종적으로 목표 좌표에 제일 많은 사탕을 가지고 갔을 때의 개수를 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int map[1001][1001];
int dp[1001][1001];

int n, x, y;
int mm(int i, int j, int k) { // 세개의 수 중 큰 수 반환
    if (i < j) i = j;
    if (i < k) i = k;
    return i;
}

int main()
{
    scanf("%d%d", &x, &y);
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    for (int i = 1; i <= x; i++) { 
        for (int j = 1; j <= y; j++) {
            dp[i][j] = mm(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + map[i][j];
        }
    }
    printf("%d", dp[x][y]);

    return 0;
}