프로그래머스 Level 4 지형편집

지형편집 (프로그래머스 Level 4)

https://school.programmers.co.kr/learn/courses/30/lessons/12984

‘개수’와 ‘높이’의 차이에 따른 비용 계산에 따라서
각각의 높이와 개수를 map으로 관리하고
‘이전 높이’와 ‘현재 높이’의 차,
그리고 ‘이전 높이’의 블록 개수들을 계산하는 방식으로 답을 구하였으나
시간 초과가 발생하였다

결국 또 많은 시간을 개선하려 시도하다 검색을 하게 되었다
‘부분합’에 가까운 해답이 가장 이해하기 쉬워 가져왔다

‘현재 높이 이전 높이들의 총합’, ‘현재 높이 이후 높이들의 총합’과
그에 따른 각각 계산해야하는 블록의 수를 구한 후
P와 Q를 곱하여 answer를 구하는 방식이다

1. 처음 시작을 위하여 ‘이후 높이들의 총합’을 미리 구한다
   
2. 이후, ‘이전 높이 총합’에 높이를 서서히 더해주며,
   ‘이후 높이 총합’은 서서히 빼준다
   
3. 현재 시점(i)에서 ‘추가해야 하는 블록의 수’는
   해당 시점의 ‘높이’와 그만큼의 ‘i’를 곱하고
   ‘이전 총합 높이’를 빼준다
   i * heights[i]는 0~부터 현재 시점까지 필요한 모든 블록의 개수이며
   preCount는 ‘이전’에 이미 존재하였던 블록의 개수이기에
   preBlock이 ‘현재 추가해야 하는 블록’의 개수를 의미할 수 있도록 해준다
   (블록이 1x1x1이기에 이렇게 계산할 수 있도록 해준다)
   
4. 현재 시점(i)에서 ‘빼줘야 하는 블록의 수’는
   ‘이후 총합 높이’에서 ‘남은 높이의 개수’ * 현재 높이 가 된다
   
5. 각각 필요한 개수에 P와 Q를 적용하여 최소 비용을 비교하고 구해준다
   

개인적으로 ‘부분합’이 여전히 어렵다고 느껴지기도 하였다
개념적인 이해가 더욱 필요할 것 같다

Code

#include<vector>
#include<limits.h>
#include<algorithm>

using namespace std;

long long solution(vector<vector<int> > land, int P, int Q) {
	vector<int> heights;
	// 현재 높이 이전의 모든 높이 합, 현재 높이 이후의 모든 높이 합
	long long preCount = 0, posCount = 0;

	// 현재 높이로 맞추기 위해 더해야하는 블록 수, 빼야 하는 블록 수
	long long preBlock = 0, posBlock = 0;
	
	for (const auto& lVec : land)
	{
		for (const auto& l : lVec)
		{
			heights.push_back(l);
			// 처음에 posCount에 다 넣어줌
			posCount += l;
		}
	}
	sort(heights.begin(), heights.end());

	const int hSize = heights.size();

	// 하나밖에 없거나,
	// 정렬 후의 처음과 끝이 같다면 계산할 필요가 없음
	if (hSize == 1 ||
		heights[hSize - 1] == heights[0])
		return 0;

	long long answer = LLONG_MAX;

	for (int i = 0; i < hSize; i++)
	{
		// 현재 높이 이전의 높이들의 총합을 preCount에 추가
		if (i > 0)
		{
			preCount += heights[i - 1];
		}

		// 현재 높이를 posCount에서 빼줌
		posCount -= heights[i];

		// preBlock: 현재 높이로 블록을 맞추기 위해 더해야 하는 블록의 수
		// 현재 높이 : heights[i]
		// 거기에 이전 블록들의 수인 i를 곱하며
		// 이전 블록 높이의 총합을 빼주어
		// '추가해야하는 블록 개수' 를 구한다
		preBlock = i * heights[i] - preCount;

		// posBlock: 현재 높이로 블록을 맞추기 위해 빼야 하는 블록의 수
		// (hSize - 1 - i) : 현재 높이 이후, 남은 높이의 개수 (i시점에서 남은 블록 수)
		posBlock = posCount - (hSize - 1 - i) * heights[i];

		// 현재 높이에서의 비용을 계산하고 최소 비용을 업데이트
		answer = min(answer, preBlock * P + posBlock * Q);
	}

	return answer;
}