[BOJ/백준 1446/C++] 지름길

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

1446번: 지름길

 

[문제 요약]

- 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다.

- 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다.

- 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

- 운전해야 하는 거리의 최솟값을 출력하시오.

 

[문제 조건]

- 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. ( 1 ≤ N ≤ 12 ) (1 ≤ D ≤ 10,000)

- 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제 자체는 굉장히 간단하다. D킬로미터까지 지름길을 이용하여 갈때 운전해야되는 최솟값을 구하면된다.

 

먼저 문제에서 가장 중요한 문장은 고속도로는 역주행 할 수 없다. 라는 말이다. 이 말인 즉, 지름길을 이용했을때 D보다 먼 곳에서 도착하면 그 지름길은 그냥 아예 안쓰면된다.

 

또한 지름길을 이용하는 것보다 시작점에서 도착점까지 그냥 가는 거리가 더 짧으면 그 지름길도 가치가 없다.

 

필자는 위 조건들을 적용시켜 처음에 가치있는 지름길들만 추려내었다.

 

다음으로는 추려낸 지름길들을 이용하여 각 거리별 운전하는데 필요한 최소거리값들을 갱신시켜주었다.

예를들어 배열의 초기값으로는 지름길을 아예 이용하지 않는 dp[i] = i의 값을 가지고 있을 것이다.

 

그 다음 지름길이 만약 입력으로 (20,50,10)이 주어진다면 20에서 50으로 10만큼의 비용으로 갈 수 있다는 뜻이니 

dp[50] = min ( dp[50] , dp[20] + 10 ) 와 같은 식으로 기존의 값과 비교하여 더 작은 값으로 갱신 시켰다.

 

그리고 하나의 지름길로 값이 갱신되면 dp[j] = min(dp[j] , dp[j-1] + 1)으로 전체적으로 최소값들을 다시 한 번 갱신시켜주었다.

 

이 과정을 모든 지름길에 대해 적용하여 정답이 된다.

 

[소스코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>
#define ppi pair<pii,int>

using namespace std;

int N, D;
vector<int> dp;
vector<ppi> fast;
bool cmp(ppi& a, ppi& b)
{
	return a.first.first < b.first.first;
}

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

	cin >> N >> D;
	dp.resize(D + 1);
	for (int i = 0; i <= D; i++) dp[i] = i;

	int s, e, c;
	for (int i = 0; i < N; i++)
	{
		cin >> s >> e >> c;
		if (s > D || e > D) continue;
		if (e - s <= c) continue;
		fast.push_back({ {s,e},c });
	}
	sort(fast.begin(), fast.end(), cmp);
	for (int i = 0; i < fast.size(); i++)
	{
		s = fast[i].first.first;
		e = fast[i].first.second;
		c = fast[i].second;
		dp[e] = min(dp[e], dp[s] + c);
		for (int j = 1; j <= D; j++) dp[j] = min(dp[j], dp[j - 1] + 1);
	}
	cout << dp[D];
}

 

 

 

굳