[C/C++] 백준 - 17484번 : 진우의 달 여행

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

17484번: 진우의 달 여행 (Small)

문제

우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

[예시]

진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.

1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.

2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.

진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.

최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

 

 

 

 

 

잘 알려진 동적계획법의 유형 중 하나이다.

하나 생각해야할 점이 전에 진행했던 방향과 같은 방향으로 진행할 수 없기 때문에 

메모이제이션을 적용할 때 현재 좌표, 전 위치에서 현 위치로 진행한 방향을 메모이제이션으로 적용해서 풀어야한다.

 

만약 현 위치를 전에 같은 방향으로 진행한 적이 있다면 이미 최소값을 가지고 있기에 진행하지 않고 값만 반환하는 방법으로 해결해준다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000007
#define endl '\n'

using namespace std;

int N, M;
int cache[8][8][4];
int board[8][8];

bool isValid(int y, int x) {
	return (0 <= y && y < N && 0 <= x && x < M);
}

int path(int y, int x, int dir) {
	if (y >= N && (0 <= x && x < M)) return 0;
	if (!isValid(y, x)) return INF;
	int &ret = cache[y][x][dir];
	if (ret != -1) return ret;

	ret = 0;
	if (dir == 1) ret = min(path(y + 1, x, 2), path(y + 1, x + 1, 3)) + board[y][x];
	else if (dir == 2) ret = min(path(y + 1, x - 1, 1), path(y + 1, x + 1, 3)) + board[y][x];
	else if (dir == 3) ret = min(path(y + 1, x - 1, 1), path(y + 1, x, 2)) + board[y][x];
	else ret = min({ path(y + 1, x - 1, 1), path(y + 1, x, 2), path(y + 1, x + 1, 3) }) + board[y][x];
	return ret;
}

int solution() {
	int Answer = INF;
	for (int i = 0; i < M; i++) {
		Answer = min(Answer, path(0, i, 0));
	}
	return Answer;
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}
	memset(cache, -1, sizeof(cache));
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}