[C/C++] 백준 - 17391번 : 무한부스터

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

17391번: 무한부스터

문제

카트라이더를 처음 시작하는 카린이 정범이는 어려운 조작법에 실망감이 커져가고 있다. 드리프트, 순간 부스터, 커팅, 톡톡이 등등 어려운 테크닉에 질린 정범이는 그나마 쉬운 ‘숭고한 무한부스터 모드’에 도전해보려고 한다.

‘숭고한 무한부스터 모드’는 크기 N × M 의 직사각형 모양의 맵에서 진행되며, 맵 전체가 단위 격자로 구성되어 있다. 기존의 ‘무한부스터 모드’와는 다르게, 모든 격자 안에는 특정 개수의 부스터 아이템이 위치한다. 이 모드에서 플레이의 방식은 다음과 같다.

처음에 플레이어의 카트바디는 출발지점인 1행 1열에 위치하며, 멈춰 있는 상태이고, 보유하고 있는 부스터 아이템의 개수는 0개이다. 목표는 도착지점인 N행 M열의 격자에 도달하는 것이며, 도달하는 즉시 게임이 종료된다. 카트바디가 격자에 멈추어 있을 때, 격자에 놓여있는 부스터 아이템을 자동으로 전부 습득하게 된다. 이 과정에서 x개를 습득했다면 한 방향을 정해 오른쪽으로 최대 x칸을 가거나, 아래쪽으로 최대 x칸을 이동할 수 있으며, 1칸 단위로 이동하게 된다. 예를 들어 부스터 아이템을 3개 습득했을 때, 오른쪽으로 2칸 이동이나 아래쪽으로 3칸 이동은 가능하지만, 오른쪽으로 1칸 이동 후 아래로 2칸 이동이나 왼쪽으로 1칸 이동이나 아래쪽으로 2.718칸 이동은 불가능하다. 이동 후 멈추면서 보유하고 있던 부스터 아이템은 모두 소진된다.

이동중에 멈추지 않고 지나치는 격자의 부스터 아이템은 습득할 수 없으며, 카트바디는 맵을 벗어나는 방향으로는 움직일 수 없다.

정범이는 ‘숭고한 무한부스터 모드’에서 출발지점부터 도착지점까지 주행하면서 부스터 아이템을 획득하게 되는 격자의 개수를 최소화하고 싶다. 카린이 정범이를 도와주도록 하자.

 

 

시작지점 (1, 1)에서 (N, M)까지 격자에서 흭득하는 아이템의 최소 개수를 구하는 문제이다.

완전탐색을 기반으로 최소 개수를 저장해주는 메모이제이션을 적용하여 동적계획법으로 해결이 가능한 전형적인 문제이다. 각 지점에서 이동 가능한 모든 경로에 대해 재귀적으로 탐색하고, 도착 지점으로 도착이 가능한 경우에만 0을 반환받아 메모이제이션 해주는 것만 체크해주면 된다.

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

using namespace std;

int N, M;
int board[300 + 1][300 + 1];
int cache[300 + 1][300 + 1];

void input() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}
}

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

int path(int y, int x) {
	// 격자 바깥으로 이동할 경우 최대값 INF를 반환하여 이동이 불가능을 알려준다.
	if (!isValid(y, x)) return INF;
	// 도착지점 (N, M)으로 이동할 경우 0을 반환해준다.
	if (y == N && x == M) return 0;
	// 메모이제이션이 적용되어 최소값이 저장되었는지 확인
	int& ret = cache[y][x];
	if (ret != -1) return ret;


	// 초기에 최대값 INF으로 저장하여 최소값을 갱신할 수 있도록 해준다.
	ret = INF;
	// 최대 1부터 아이템 개수만큼 정해진 방향으로만 이동 가능하기 때문에 모든 경우 확인해준다.
	for (int i = 1; i <= board[y][x]; i++) {
		ret = min(ret, path(y + i, x)+1);
		ret = min(ret, path(y, x + i)+1);
	}
	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return path(1, 1);
}

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

	return 0;
}