문제접근
•
각 조의 비용을 구할때 원소 간 차이를 구하게 된다. 따라서 원소 간 차이를 저장하고 원소 간 차이가 가장 큰 부분은 혼자 두면 된다.
•
조가 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);
}
C++
복사
