Search
Duplicate
๐Ÿฅˆ

์ด๋™ํ•˜๊ธฐ

์ฃผ์ฐจ
13
๋ฌธ์ œ๋ฒˆํ˜ธ
11048
์–ธ์–ด
ํ‹ฐ์–ด
์‹ค๋ฒ„
์œ ํ˜•
DP
nj_Blog
O
nj_์ƒํƒœ
์™„๋ฃŒ
์ดํ•ด๋„
ํ’€์ด
์‚ฌ๋žŒ
์ดํ•ด๋„ 2
13 more properties

๋ฌธ์ œ๋งํฌ

์ฝ”๋“œ ์ œ์ถœ ๊ธฐ๋ก (๋ฉ”๋ชจ๋ฆฌ ๋ฐ ์‹œ๊ฐ„)

๋ฉ”๋ชจ๋ฆฌ : 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
๋ณต์‚ฌ