[C++] 알리바바와 40인의 도둑

📄문제

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.
알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다.
계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.
해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다.
즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다.
N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요.
만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면

(1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다.

 

⬇️ 입력

첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다.
두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.

5 3 7 2 1 9 5 8 3 9 2 5 3 1 2 3 5 4 3 2 1 1 7 5 2 4

 

⬆️ 출력

첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.

25

 

📝 풀이

#include <iostream>
using namespace std;

int dp[21][21];
int arr[21][21];

int main()
{
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			cin >> arr[i][j];

	dp[1][1] = arr[1][1];

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (i == 1 && j != 1)
				dp[i][j] = dp[i][j - 1] + arr[i][j];
			else if (j == 1 && i != 1)
				dp[i][j] = dp[i - 1][j] + arr[i][j];
			else
			{
				// 위 누적값이 왼쪽 누적값보다 작으면?(최저)
				if (dp[i][j - 1] < dp[i - 1][j])
					dp[i][j] = dp[i][j - 1] + arr[i][j];
				else
					dp[i][j] = dp[i - 1][j] + arr[i][j];
			}
		}
	}

	cout << dp[N][N];
}

• 이 문제는 1, 1위치에서 N,N으로 이동할 때 무조건 오른쪽 또는 왼쪽으로 이동합니다.
• 그렇지 않으면, 거리에 손해를 보기때문에 두가지만 생각합니다.
• 다음 위치가 가장자리와 가장자리가 아닌경우 서로 계산식이 다릅니다.
• 위 코드는 bottom-up 방식으로 for문을 이용하여 계산합니다.

 

#include <iostream>
using namespace std;

int dp[21][21];
int arr[21][21];

int DFS(int x, int y)
{
	if (dp[x][y] != 0)
		return dp[x][y];
	else if (x == 1 && y != 1)
		return  dp[x][y] = DFS(x, y - 1) + arr[x][y];
	else if (x != 1 && y == 1)
		return  dp[x][y] = DFS(x - 1, y) + arr[x][y];
	else
		return dp[x][y] = min(DFS(x - 1, y), DFS(x, y - 1)) + arr[x][y];
}

int main()
{
	ios_base::sync_with_stdio(false);

	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			cin >> arr[i][j];

	dp[1][1] = arr[1][1];

	cout << DFS(N, N);
}

• 계산을 위한 식은 동일하지만, top-down 방식으로 구현하였습니다.