[C/C++] 백준 - 1446번 : 지름길

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

1446번: 지름길

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

 

가야하는 길이를 지름길과 고속도로를 이용하여 최소 비용으로 가야한다.

나는 이 문제를 냅색문제처럼 이해하여 지름길을 통하여 가는 방법과 지름길을 이용하지 않고 고속도로를 이용하는 방법을 선택하여 구해보았다.

 

현재 나의 시작점을 재귀 함수 매개변수로 넘겨주고, 현재 위치에서 고속도로만을 이용시키는 방법과 현재 인덱스 지름길의 시작지점을 이용할 수 있다면 지름길로 가보는 비용을 비교하여 메모이제이션을 적용시켜주는 방법이다.

#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 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N, D;
const int MAX = 12;
int cache[MAX + 1][10001];
vector<pair<int, pair<int, int>>> ps;

bool cmp(const pair<int, pair<int, int>> lhs, const pair<int, pair<int, int>> rhs) {
	if (lhs.first == rhs.first) return lhs.second.first < rhs.second.first;
	return lhs.first < rhs.first;
}

void input() {
	cin >> N >> D;
	for (int i = 0; i < N; i++) {
		int s, e, l; cin >> s >> e >> l;
		ps.push_back({ s, {e,l} });
	}
}

int path(int index, int start, int last) {
	if (start == last) return 0;
	if (index == N) return last - start;
	int& ret = cache[index][start];
	if (ret != -1) return ret;

	ret = 0;
	ret = path(index + 1, start, last);
	if (start <= ps[index].first && ps[index].second.first <= last)
		ret = min(ret, path(index + 1, ps[index].second.first, last) + ps[index].second.second + ps[index].first - start);
	return ret;
}

int solution() {
	sort(ps.begin(), ps.end());
	memset(cache, -1, sizeof(cache));
	return path(0, 0, D);
}

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