문제접근🤔

각 조의 비용을 구할때 원소 간 차이를 구하게 된다. 따라서 원소 간 차이를 저장하고 원소 간 차이가 가장 큰 부분은 혼자 두면 된다.
조가 k개이기 때문에 원소 간 차이의 배열은 k-1이 된다. for문은 k - 1개 만큼 돌아야 하기 때문에 n - 1 - (k - 1)개 만큼, 즉 n - k번 만큼 돌면된다. n - 1을 하는 이유는 현재 n은 전체 수이고 우리는 원소 간 차이의 배열이 필요했던거기 때문에 배열 크기가 n - 1이다

놓쳤던 부분😅

메모리를 아끼기 위해 별도의 벡터 없이 cost 벡터로만 하려다보니 n - k의 유도 과정에서 n - 1이 왜 필요한지 헷갈렸음
- 처음의 n은 학생수, 우리는 원소 간 차이의 값을 담게 되면서 기존보다 n에서 n-1의 배열이 되었는데, 현재의 cost벡터에는 마지막에 불필요한 값이 담겨져있음(원소 간 차가 아니라 원래 값).
- cost 벡터의 역할이 바뀌었다고 생각하면 됨. 처음 : 학생의 키, 이후 : 옆사람끼리의 학생 키의 차. 따라서 마지막 원소에 학생 키의 차가 담긴게 아니라 학생의 키가 담겨있음.

코드😁

4368 KB

56 ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	int n, k;
	vector<long long> cost;
	int answer = 0;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	cost.resize(n);

	cin >> cost[0];
	for (int i = 1; i < n; i++)
	{
		cin >> cost[i];
		cost[i - 1] = cost[i] - cost[i - 1];
	}
	sort(cost.begin(), cost.end());
	for (int i = 0; i < n - k; i++)
		answer += cost[i];
	cout << answer;
	return (0);
}