λ©λͺ¨λ¦¬ : 37064KB
μκ° : 1000ms
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [[0] * (M + 1)] * (N + 1)
candy = []
for i in range(N):
candy.append(list(map(int, input().split())))
for i in range(1, N+1):
for j in range(1, M+1):
dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]
print(dp[N][M])
#include <iostream>
#include <algorithm>
int N, M;
int dp[1001][1001];
int candy[1001][1001];
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> N >> M;
for (int i = 1 ; i <= N ; i++)
for (int j = 1; j <= M ; j++)
std::cin >> candy[i][j];
}
void solve()
{
for (int i = 1 ; i <= N ; i++)
for (int j = 1 ; j <= M ; j++)
dp[i][j] = std::max(std::max(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + candy[i][j];
}
void print_val()
{
std::cout << dp[N][M];
}
int main()
{
input_faster();
input();
solve();
print_val();
return (0);
}
<λ¬Έμ μ κ·Ό>
dp[N][M] λ₯Ό ꡬν μ μλ κ²½μ°μ μλ μ΄ 3κ°μ§λ‘
μμ κ²½μ° λ€μ λͺ¨λ ꡬν΄μ κ·Έ μ€μ κ°μ₯ ν° κ°μ dp[N][M]λ‘ κ²°μ νλ©΄ λλ€