[BAE/<JOON> 문제풀이] 1866. 택배

www.acmicpc.net/problem/1866

1866번: 택배

서론||

드디어 혼자 힘으로 플레 이상 문제를 하나 풀어봤다.

 

항상 정올 문제들이 어렵다고 생각했는데 같은 티어 문제에 비해서 정올 문제가 그나마 쉬운 것 같다.

 

 

풀이||

예제는 문제에 나와있는 예제 입력 사용

 

우선 각각의 배송지들을 거리순으로 정렬하고 각 지점에서 헬기를 이용한다고 가정하여

 

다음과 같이 거리 테이블을 만들어낸다.

 

0(H)	100	100	300	400	500
0	200(H)	0	200	300	400
0	0	200(H)	200	300	400
0	200	200	200(H)	100	200
0	300	300	100	200(H)	100
0	400	400	200	100	200(H)

(H)기호는 해당 지점에서 헬기를 사용하여 배달한 거리임을 의미함.

 

1열은 1행 즉, 헬기를 사용하지 않고 본점에서 모두 배달하는 것을 이해하기 쉽게 하기 위해 만든 것이니 무시해도 좋다.

 

이 테이블을 가지고 다수의 헬기를 이용할 때의 비용 계산을 직관적으로 해 낼 수 있다.

 

DP[i][j] = i행의 j열까지의 헬기를 이용한 최소 배달 비용으로 놓고 DP 테이블을 채워나가보자.

 

(이하 DP = DP테이블, TAB = 위에서 계산한 값 테이블

 

DP[i]행은 DP[i][i] 지점에서 헬기를 이용했을 때를 기준으로 계산한 비용이다.

 

따라서 DP[i][i]이전의 값들은 DP[i][i]까지는 사용할 수 없는 값들이다.

 

(현재 헬기를 이용하지 않은 지점이므로 이전에 헬기를 이용했던 테이블과 함께 계산을 하게되면 현재 헬기를 사용하지도 않았는데 현재 헬기를 이용해 배달한 비용만 사용하는 꼴이된다.)

 

따라서 DP[i - 1]행에서 계산한 값들을 그대로 채워넣는다. i번째 열부터는 3가지 선택지가 있다.

 

점화식||

1. DP[i - 1][j] {j > i} 현재 헬기를 사용하지 않는 경우

 

2. DP[i][j - 1] + TAB[i][j] {j > i} 현재 헬기를 사용하는 경우

 

3. MIN( SUM(TAB[i][i - 1] ~ TAB[i][i - k]) + DP[i - 1][i - k - 1] ) {1 < k < i}

현재 헬기를 이용하고 1~i-1사이에 있는 배달 지점에도 현재 헬기를 사용해서 배달하는 경우

 

결과 도출||

1번과 2번은 i+1지점 부터 N까지를 계산하는 항이고 3번이 i지점을 계산하는 항이다.

 

이 부분에서 함정이 있다. DP[i][j]는 항상 i행 j열까지의 최솟값을 저장한다.

 

DP[i][i]항을 계산 할 때 1번항이 2번항이나 3번항보다 최적값이서 DP[i][i]에 1번항 값이 적혔다고 생각해보자.

 

그럼 다음 j + 1 지점을 계산시 위의 점화식 만으로 2항을 올바르게 계산할 수 있을까? 틀린다.

 

DP[i][i]를 계산 할 때 DP[i - 1][j] 즉, 이전 헬기 값을 선택한 경우는 현재 헬기를 사용하지 않고 계산한값이다.

 

따라서 현재 헬기를 사용한 비용이 적혀있는 TAB[i]행의 값들을 사용하면 틀린 결과가 나오는 것이다.

 

그래서  DP[i][i]항을 계산 할 때 최적값이든 아니든 현재 헬기를 사용한 최솟값을 따로 구해서 가지고 있을 필요가 있다.

 

현재 헬기를 사용하여 배달한 값이 이전 헬기를 사용해 배달한 값보다 더 작아지면 그때부터 DP[i]행을 사용해서

 

2번항만을 계산하고 그전까지는 따로 구한 현재 헬기를 이용한 최솟값을 사용해서 1, 2번항을 비교하며 DP테이블을 채워넣는다.

 

현재 행의 모든 원소들에 대해서 현재 헬기가 이전 헬기보다 가까우므로 항상 값이 갱신된다는 것이 보장된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	cin >> n;
	arr = vector<int>(n + 1);
	dp = vector<vector<int>>(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	sort(arr.begin(), arr.end());
	cin >> t >> h;
	for (int i = 1; i <= 10000; i++) {
		dt[i] = dt[i - 1] + t;
	}
	for (int j = 1; j <= n; j++) {
		tab[0][j] = dt[arr[j]];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				tab[i][j] = h;
				continue;
			}
			tab[i][j] = abs(dt[arr[i]] - dt[arr[j]]);
		}
	}

	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[0][i] = dp[0][i - 1] + tab[0][i];
	}
	for (int i = 1; i <= n; i++) {
		int min = tab[i][i] + dp[i - 1][i - 1];
		int sum = tab[i][i];
		for (int j = i - 1; j >= 1; j--) {
			dp[i][j] = dp[i - 1][j];
			sum += tab[i][j];
			min = min < sum + dp[i - 1][j - 1] ? min : sum + dp[i - 1][j - 1];
		}
		int sv = dp[i][i - 1] + tab[i][i];
		sv = sv < min ? sv : min;
		bool hcb = dp[i - 1][i] >= sv;
		dp[i][i] = sv < dp[i - 1][i] ? sv : dp[i - 1][i];
		for (int j = i + 1; j <= n; j++) {
			if (hcb) {
				dp[i][j] = dp[i][j - 1] + tab[i][j];
			}
			else {
				int s1 = dp[i - 1][j];
				int s2 = sv + tab[i][j];
				dp[i][j] = s1 < s2 ? s1 : s2;
				sv += tab[i][j];
				if (s1 >= s2) hcb = true;
			}
		}
	}

	/*for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}*/
	cout << dp[n][n];
	return 0;
}