🍋 문제링크

11048번: 이동하기

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 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])

#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-1][M] + candy
• dp[N][M-1] + candy
• dp[N-1][M-1] + candy

위의 경우 들을 모두 구해서 그 중의 가장 큰 값을 dp[N][M]로 결정하면 된다