240131 지형 편집

Jongleee·2024년 1월 31일
0

TIL

목록 보기
483/737
public long solution(int[][] land, int p, int q) {
	long answer;
	long maxHeight = 0;
	long minHeight = Long.MAX_VALUE;
	long totalBlocks = 0;

	for (int i = 0; i < land.length; i++) {
		for (int j = 0; j < land[i].length; j++) {
			maxHeight = Math.max(maxHeight, land[i][j]);
			minHeight = Math.min(minHeight, land[i][j]);
			totalBlocks += land[i][j];
		}
	}

	answer = calculateCost(land, maxHeight, p, q, totalBlocks);

	long front = minHeight;
	long rear = maxHeight;

	while (front <= rear) {
		long mid = (front + rear) / 2;
		long cost1 = calculateCost(land, mid, p, q, totalBlocks);
		long cost2 = calculateCost(land, mid + 1, p, q, totalBlocks);

		if (cost1 <= cost2) {
			answer = cost1;
			rear = mid - 1;
		} else {
			answer = cost2;
			front = mid + 1;
		}
	}

	return answer;
}

private long calculateCost(int[][] land, long height, int p, int q, long totalBlocks) {
	long cost = 0;

	for (int i = 0; i < land.length; i++) {
		for (int j = 0; j < land[i].length; j++) {
			if (land[i][j] < height) {
				cost += (height - land[i][j]) * p;
			} else if (land[i][j] > height) {
				cost += (land[i][j] - height) * q;
			}
		}
	}

	return cost;
}

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

0개의 댓글