[백준/C++] 2651 자동차 경주대회

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

2651번: 자동차경주대회

문제 분석

난이도

골드 4

분류

구현, DP

들어가기 전에

DP이지만 입력이랑 예외처리가 상당히 까다로운 문제, 최소값만 구하는 것이라면 별로 어려운 문제가 아니지만 개수구하기 + 역추적 까지 해야하는 문제

 

문제 풀이

문제 해결을 조금 더 수월하게 하기 위해서 거리를 누적해서 저장해 주었다. 현재 지점과 선택한 지점의 누적된 값을 빼면 거리를 구할 수 있고 그 거리가 k보다 작다면 대소비교를 하고, 작다면 값을 최신화 해주고 그 위치를 저장해주었다.

반복하면 목적지까지 도달 하였을 때 최소로 걸린 시간을 구할 수 있고, 그때마다 이전 위치를 계속 저장해준 배열을 이용하여 거쳐간 정비소의 개수와 거쳐간 정비소의 번호를 출력해주면 된다

소스코드

 

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int mx, n, arr[102];
	int time[102] = { 0, };
	int dist[102] = { 0, };
	long long dp[102] = { 0, };
	int before[102] = { 0, };

	for (auto& i : dp) i = 2147483648;
	dp[0] = 0;
	cin >> mx >> n;
	if (n == 0)
	{
		cout << "0\n0";
		return 0;
	}
	for (int i = 0; i <= n; i++) cin >> arr[i];
	for (int i = 0; i <= n; i++) dist[i + 1] = dist[i] + arr[i];
	for (int i = 0; i < n; i++) cin >> time[i];

	for (int i = 1; i <= n + 1; i++)
	{
		int idx = i - 1;
		while (idx >= 0 && dist[i] - dist[idx] <= mx)
		{
			if (dp[i] > dp[idx] + time[i - 1])
			{
				dp[i] = dp[idx] + time[i - 1];
				before[i] = idx;
			}
			idx -= 1;
		}
	}
	cout << dp[n+1] << "\n";
	int cnt = 0;
	int now = n+1;
	int ans[102] = {0,};
	while (before[now])
	{
		cnt++;
		ans[cnt] = before[now];
		now = before[now];
	}
	cout << cnt << "\n";
	while (cnt)
	{
		cout << ans[cnt--] << " ";
	}
}