백준 2651번 - 자동자경주대회 (C++)

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

2651번: 자동차경주대회

 

어떤 코테에서 봤던 문제인 것 같다. 역시나 코테의 문제들은 모두 백준에 존재한다. 많이 풀어보고 완벽하게 익히고 있어야한다. 

 

먼저 이 문제를 봤을 때 떠올랐던 풀이는 다익스트라, 배낭문제, 다이나믹 프로그래밍이었다. 

dp[N][2] 를 선언하고 충전을 하였을 때와 안하였을 때를 넣으려고 했는데 생각보다 잘 안됐다. 

 

이 문제를 해결하기 위해 필요한 건 글쎄,, 이런 문제를 풀어본 경험 혹은 아주 뛰어난 실력이랄까

 

아무튼, 

 

 

위의 예제를 누적 거리로 표현하면 다음과 같다.

 

dist[0] = 0

dist[1] = 100

dist[2] = 130

dist[3] = 230

dist[4] = 270

dist[5] = 320

dist[6] = 380

 

여기서 유추할 수 있는 건 dist[i] - dist[i - 1] 은 위 사진의 i - 1~ i 까지가는 비용이 된다. 그리고 dist[i] - dist[i - 2] 는 i - 2~ i 까지 가는 비용이다. 즉 dist[i] - dist[i - x] 가 주어진 최대 이동거리보다 크다면 쉬지않고 갈 수 있다는 의미이다.

이 수학적 원리를 사용하여 문제를 풀 수 있다.

 

for (int i = 1; i <= N + 1; i++) {
		for (int j = i - 1; j > -1; j--) {
			if (dist[i] - dist[j] > HP) {
				break;
			}
			if (dp[i] > dp[j] + mapping[j]) {
				dp[i] = dp[j] + mapping[j];
				log[i] = j;
			}
		}
	}

   

위 코드를 해석해보면, j번째부터 i 번째 까지 이동이 가능하다면 j - 1부터 i 번째도 한번에 갈 수 있는지 확인한다. 만약 한번에 갈 수 없다면 break한다. 왜냐하면 만약 1에서 쉬더라도 4까지는 도달할 수 없기 때문에 둘의 관계는 보지 않아도 된다. 그러나 쉬지 않는다고 꼭 정답이 아니다. 만약 그랬다면 이 문제는 dp가 아니라 그리디였을 것이다. 

 

그러므로 만약 현재 dp값보다 dp[j]에서 쉬는것이 이득인지 아닌지도 따져본다. 그리고 최대거리로 도달할 수 없을 때 까지 반복하기 때문에 중간에 한번은 쉬는 타임이 있어야한다. 그것이 어딘지 찾는 과정이다. 

 

또한 이 문제는 로그까지 던져줘야한다. 

 

그래서 log[i] = j를 기록한다. 이 의미는 i에 가기 위해서는 j가 필요하다는 의미이다. 

그렇다면 마지막 6을 가기위해서는 무언가가 기록될 것이고

그 log[무언가] 에는 또 무언가를 가기위한 무언가가 기록될 것이니 꼬리물기를 하며 log를 기록할 수 있다. 

 

매우 좋지만 까다로운 문제라고 생각한다. 딱 코테문제이기도 해서 두고두고 복습해야겠다.

 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
map<int, int> mapping;
long long dp[105];
long long dist[105];	
int log[105];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int HP, N;
	cin >> HP >> N;
	dist[0] = 0;
	for (int i = 1; i < N + 2; i++) {
		int n;
		cin >> n;		
		dp[i] = 5465418451;

		dist[i] = n + dist[i - 1];
	}

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		mapping.insert({ i + 1, tmp });
	}
	dp[0] = 0;
	for (int i = 1; i <= N + 1; i++) {
		for (int j = i - 1; j > -1; j--) {
			if (dist[i] - dist[j] > HP) {
				break;
			}
			if (dp[i] > dp[j] + mapping[j]) {
				dp[i] = dp[j] + mapping[j];
				log[i] = j;
			}
		}
	}

	cout << dp[N + 1] << '\n';
	
	int tmp = log[N + 1];

	vector<int> log_vec;

	while (tmp != 0) {
		log_vec.push_back(tmp);
		tmp = log[tmp];
	}
	sort(log_vec.begin(), log_vec.end());
	cout << log_vec.size() << '\n';
	for (auto a : log_vec) cout << a << " ";
}