๋ฌธ์ ๋งํฌ
์ฝ๋ ์ ์ถ ๊ธฐ๋ก (๋ฉ๋ชจ๋ฆฌ ๋ฐ ์๊ฐ)
๋ฉ๋ชจ๋ฆฌ : 37064KB
์๊ฐ : 1000ms
Code
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])
Python
๋ณต์ฌ
#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);
}
C++
๋ณต์ฌ
๋ฉ๋ชจ
<๋ฌธ์ ์ ๊ทผ>
dp[N][M] ๋ฅผ ๊ตฌํ ์ ์๋ ๊ฒฝ์ฐ์ ์๋ ์ด 3๊ฐ์ง๋ก
โข
dp[N-1][M] + candy
โข
dp[N][M-1] + candy
โข
dp[N-1][M-1] + candy
์์ ๊ฒฝ์ฐ ๋ค์ ๋ชจ๋ ๊ตฌํด์ ๊ทธ ์ค์ ๊ฐ์ฅ ํฐ ๊ฐ์ dp[N][M]๋ก ๊ฒฐ์ ํ๋ฉด ๋๋ค
<python : 2์ฐจ์ ๋ฐฐ์ด ์
๋ ฅ๋ฐ๊ธฐ>
for i in range(N):
arr.append(list(map(int, input().split())))
Python
๋ณต์ฌ