[Programmers] 지형 편집

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12984

코딩테스트 연습 - 지형 편집

이분 탐색을 이용해서 푸는 문제였습니다.

이차원 벡터를 매개변수로 넘길 때 참조형으로 넘기는 경우가 훨씬 빠르니 참조형으로 전달해야 합니다.

 

알고리즘은 아래와 같습니다.

1. 주어진 벡터에서 최소 층과 최대 층을 구한 뒤 이를 기준으로 이분 탐색을 진행합니다.

2. mid와 mid + 1 층을 기준으로 비용을 구한 뒤 더 작은 쪽을 기준으로 범위를 좁혀가며 이분 탐색을 진행합니다.

3. 2번 과정을 거친 뒤 최소 비용을 반환해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <climits>
	using namespace std;
	const int MAX = 1e9 + 1e7;
	long long getTotalCost(long long mid, vector<vector<int>> &land, int P, int Q)
	{
	long long cost = 0;
	for (int i = 0; i < land.size(); i++)
	{
	for (int j = 0; j < land.size(); j++)
	{
	long long diff = land[i][j] * 1LL - mid;
	cost += diff >= 0 ? diff * Q : diff * -P;
	}
	}
	return cost;
	}
	long long solution(vector<vector<int> > land, int P, int Q) {
	long long left = LLONG_MAX;
	long long right = 0;
	for (int i = 0; i < land.size(); i++)
	{
	for (int j = 0; j < land.size(); j++)
	{
	left = min(left, land[i][j] * 1LL);
	right = max(right, land[i][j] * 1LL);
	}
	}
	long long answer = LLONG_MAX;
	while (left <= right)
	{
	long long mid = (left + right) / 2;
	long long candidate = getTotalCost(mid, land, P, Q);
	long long candidate2 = getTotalCost(mid + 1, land, P, Q);
	if (candidate == candidate2)
	{
	answer = min(answer, candidate);
	break;
	}
	if (candidate > candidate2)
	{
	answer = min(answer, candidate2);
	left = mid + 1;
	}
	else if (candidate < candidate2)
	{
	answer = min(answer, candidate);
	right = mid - 1;
	}
	}
	return answer;
	}
	int main(void)
	{
	vector<vector<int>> land = {
	{ 4, 4, 3 },
	{ 3, 2, 2 },
	{ 2, 1, 0 }
	};
	int P = 5;
	int Q = 3;
	cout << solution(land, P, Q) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~