🙇‍♀️알리바바와 40인의 도둑(Bottom-Up)

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.

알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다.

계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.

해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다.

즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다.

N*N의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의 최소량을 구하는 프로그램을 작성하세요.

만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면

3 3 5
2 3 4
6 5 2

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

▣ 입력설명
첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다. 

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

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

▣ 입력예제 1 
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
25

🚀풀이

동적 계획법 문제이다.

dp의 값은 그 위치로 도달하는 최소 코스트를 나타낸다.

해당 위치에서 위의 dp값, 왼쪽의 dp값을 비교해서 작은 값을 택하고 자기 자신의 코스트를 더해주면 해당위치 dp값이 된다.

dp[y][x] = board[y][x] + min(dp[y - 1][x], dp[y][x - 1]);

맨 윗줄과 왼쪽줄은 처음에 바로 dp값을 넣어줘야한다.

dp[i][1] = dp[i - 1][1] + board[i][1];
dp[1][i] = dp[1][i - 1] + board[1][i];

void solve()
{
	dp[1][1] = board[1][1];
	for (int i = 2; i <= n; ++i)
	{
		dp[i][1] = dp[i - 1][1] + board[i][1];
		dp[1][i] = dp[1][i - 1] + board[1][i];
	}

	for (int y = 2; y <= n; ++y)
	{
		for (int x = 2; x <= n; ++x)
		{
			dp[y][x] = board[y][x] + min(dp[y - 1][x], dp[y][x - 1]);
		}
	}

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

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<vector<int>> board, dp;
void setting()
{
	cin >> n;
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	dp = vector<vector<int>>(n + 1, vector<int>(n + 1, 123456789));

	for (int y = 1; y <= n; ++y)
		for (int x = 1; x <= n; ++x)
		{
			cin >> board[y][x];
		}
}

void solve()
{
	dp[1][1] = board[1][1];
	for (int i = 2; i <= n; ++i)
	{
		dp[i][1] = dp[i - 1][1] + board[i][1];
		dp[1][i] = dp[1][i - 1] + board[1][i];
	}

	for (int y = 2; y <= n; ++y)
	{
		for (int x = 2; x <= n; ++x)
		{
			dp[y][x] = board[y][x] + min(dp[y - 1][x], dp[y][x - 1]);
		}
	}

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

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고