문제

problem

접근 방법

이 문제는 어떻게 해결하는 것이 좋을까요? 제가 문제에 접근한 방법은 이렇습니다:

-입력 값들을 저장한 벡터를 nums라 합니다.

-각 원소들의 차이를 저장한 벡터를 gaps라 합니다.

우리가 찾고자 하는 값은, 가장 큰 키에서 가장 작은 키를 뺀 값에서 gaps 중 큰 순서대로 K-1 개의 원소를 모두 더한 값을 빼준 것과 같습니다. 따라서 그 식은 result = (nums[N-1] - nums[0]) - gap 로 나타낼 수 있습니다. 여기서 gap은, gaps의 값들 중에서 가장 큰 K-1개의 원소들을 골라 모두 더한 값입니다.

코드

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

using namespace std; 

bool desc(int a, int b) {
	return a > b; 
}

int main()
{
	int N, K; 
	cin >> N >> K;

	vector<int> nums; 
	vector<int> gaps; 

	int num; 
	for (int i = 0; i < N; i++) {
		cin >> num; 
		nums.push_back(num); 
	}

	for (int i = 0; i < N-1; i++) {
		gaps.push_back(nums[i+1] - nums[i]); 
	}

	sort(gaps.begin(), gaps.end(), desc);
	int gap = 0; 

	for (int i = 0; i < K-1; i++) {
		gap += gaps[i]; 
	}

	int result; 
	result = (nums[N-1] - nums[0]) - gap; 
	cout << result; 

}

C++

작년까지만 해도 계속해서 C를 써오다가, 새해를 맞이하여 라이브러리 함수가 다양한 C++로 사용언어를 바꾸고자 합니다. C로 이 문제를 풀었다면 배열 공간을 동적할당하는 것 뿐만 아니라 정렬 알고리즘 또한 직접 구현 했어야 했을 것입니다. C++에는 헤더 파일에 이미 sort 함수가 있고, 이를 가져다 쓰니 문제풀이 시간이 훨씬 단축될 수 있었습니다.