[백준/BOJ] 백준 27114번 : 조교의 맹연습

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

27114번: 조교의 맹연습

 

cache[남은 에너지][현재 방향]에 남은 에너지를 모두 다 쓰고, 처음 방향으로 돌아가는 최소 연산 횟수를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> e;
int k;

vector<vector<int>> cache(1000005, vector<int>(4, -1)); //[남은 에너지][현재 방향] = 남은 에너지를 모두 다 쓰고, 처음 방향(1번 방향)으로 돌아 가는 최소 연산 횟수

//dir: 0 왼쪽 방향, 1 정면 방향(처음 방향), 2 오른쪽 방향, 3 뒤쪽 방향
int solve(int remain, int dir) {

	if (remain == 0) { //에너지를 다 썻을때
		if (dir == 1) { //처음 방향으로 돌아 왔을때
			return 0;
		}
		else { //처음 방향으로 돌아오지 못했을때
			return 987654321;
		}
	}

	else if (remain < 0) { //에너지를 초과 소비 했을때
		return 987654321;
	}

	int& ret = cache[remain][dir];

	if (ret != -1) {
		return ret;
	}

	ret = 987654321;
	int next_dir;

	//좌로 돌아를 할때
	next_dir = dir - 1;
	if (next_dir < 0) {
		next_dir = 3;
	}
	ret = min(ret, solve(remain - e[0], next_dir) + 1);

	//우로 돌아를 할때
	next_dir = dir + 1;
	if (next_dir > 3) {
		next_dir = 0;
	}
	ret = min(ret, solve(remain - e[1], next_dir) + 1);

	//뒤로 돌아를 할때
	if (dir == 0 || dir == 1) {
		next_dir = dir + 2;
	}
	else {
		next_dir = dir - 2;
	}
	ret = min(ret, solve(remain - e[2], next_dir) + 1);

	return ret;
}

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

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input;

		e.push_back(input);
	}

	cin >> k;

	int result = solve(k, 1);

	if (result == 987654321) {
		cout << -1 << "\n";
	}
	else {
		cout << result << "\n";
	}

	return 0;
}