[Codeup] 3703. 사탕 줍기 1

1. 문제 링크

https://codeup.kr/problem.php?id=3703

코드업

 

2. 문제 풀이

(1,1)에서 (N,M) 까지 가면서 사탕을 최대한 많이 얻어가야 한다.

또, 맵의 상,하,좌,우를 방문 가능한 것처럼 적혀있지만, 다 방문할 필요가 없다.

 

이유는 '가장 짧은 길로 가면서 사탕을 최대한 많이 얻는 것이 목표'이다.

따라서, 최단 경로만 고려하면 위나 왼쪽으로 이동하는 경로는 제외할 수 있고, 맵의 아래나 오른쪽으로만 가면 된다.

 

이동 할 때, 이전에 얻어올 수 있는 사탕의 개수의 최대 값에 해당 칸에서 얻을 수 있는 사탕의 개수를 누적하는 방식으로 계산해 나가면 마지막 도착할 때 최대 사탕의 개수를 구할 수 있다.

 

3. 아이디어

1. 특정 칸에 도달했을 때 얻을 수 있는 최대 사탕의 수는 자신의 바로 윗쪽 칸에서 얻어온 사탕의 누적 개수 또는 왼쪽 칸에서 얻어온 사탕의 누적 개수 중 큰 값에 지금 현재 위치에서 얻을 수 있는 사탕의 개수를 더하면 된다.
2. 이를 배열로 표현하면 dp[i][j] 형태로 표현할 수 있는데, dp[i][j]는 (i,j)에 방문 했을 때 얻을 수 있는 최대 사탕의 수이다.
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + candy[i][j]; 와 같은 형태가 된다.

 

4. 구현

※ C++ Source Code

#include <iostream>
using namespace std;
int max(int x, int y)
{
	return x >= y ? x : y;
}
int main(void)
{
	int candy[105][105];
	int dp[105][105] = { 0 };
	int n, m;

	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> candy[i][j];
		}
	}

	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]) + candy[i][j];
			// 현재 위치에서 얻을 수 있는 사탕의 최대 개수는
			// 왼쪽에서 온 경우에 대한 사탕의 최대 개수 
		}
	}

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