백준 11048번 이동하기

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp

int n, m;
int map[1001][1001];
int dp[1001][1001];

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> map[i][j];
}


void SOLVE()
{

	// Bottom Up Dynamic Programming
	/*
	* dp[x][y] : map[x][y]지점까지 가져올 수 있는 사탕의 최대값
	* 
	* 대각선 아래 방향으로 갈 수 있으나, 사탕 개수가 음수인 경우는 없으므로
	* 바로 대각선 아래로 가는 것이 아닌,
	* 아래나 오른쪽을 거친 후 가는 것이 반드시 더 크거나 같다.(0은 가능하므로)
	* 
	* 따라서, dp[x][y]에서 왼쪽값과 윗쪽값. 즉,
	* map[x][y - 1]과 map[x - 1][y]중 더 큰 값에 map[x][y] 지점의 사탕을
	* 더해준 값이 dp[x][y]이 된다.
	* 
	* 결론적으로 점화식은
	* dp[x][y] = max(dp[x][y - 1], dp[x - 1][y]) + map[x][y]
	* 
	* 이중for문으로 순회하며 dp값을 구한 뒤,
	* dp[n][m]을 출력하면 답!
	* 
	*/
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + map[i][j];

	cout << dp[n][m];
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.