[PS][DP] BOJ 17485 : 진우의 달 여행(Large)

[2021년 08월 13일 11시 07분 작성]

[PS][DP] BOJ 17485 : 진우의 달 여행(Large)

---

[문제 링크 : 클릭]

---

1. 풀이

[BOJ 17484] 문제에서 값의 범위가 더 커진 문제입니다.

위 문제에서 정의한 함수에 메모이제이션을 적용시켜주면 해결이 가능합니다.

 

Solve(y, x, last) : 현재 좌표가 (y, x)이고, 마지막으로 움직인 방향이 last일 때,                       우주선이 달까지 가는데에 필요한 연료의 최소값

---

2. 소스코드

[Github 링크 : 클릭]

#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
const int dx[3] = {-1, 0, 1};
int n, m, ans=INF, board[1001][1001];
int cache[1001][1001][3];

int Solve(int y, int x, int last)
{
	int &ret = cache[y][x][last];
	if(ret!=-1) return ret;
	if(y==n) return 0;

	ret = INF;
	for(int i=0; i<3; i++)
	{
		if(last==i) continue;
		if(x+dx[i]<0 || x+dx[i]>=m) continue;

		ret = min(ret, Solve(y+1, x+dx[i], i) + board[y][x]);
	}
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin>>n>>m;

	memset(cache, -1, sizeof(cache));
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin>>board[i][j];

	for(int i=0; i<m; i++)
		for(int j=0; j<3; j++)
			ans = min(ans, Solve(0, i, j));

	cout<<ans<<'\n';

	return 0;	
}

---

3. 복기

.