지형 편집
문제 풀이 시간 : 38분
문제 요약
- •
게임 지형은 각 칸마다 정수 높이를 가지고 있음
- •
목표 : 모든 칸의 높이를 동일하게 만들기
- •
블록 1개를 쌓는 비용 =
P
- •
블록 1개를 제거하는 비용 =
Q
- •
최종적으로 모든 칸의 높이가 같아지도록 할 때 필요한 최소 비용을 구하는 문제
문제 풀이
처음 보자마자
모든 칸의 높이를 하나씩 골라가며 계산하면 답이 나오긴 하겠지만,
높이 값이 0 ~ 10억 범위이기 때문에 단순 완전탐색으로는 절대 해결할 수 없다는 걸 바로 알 수 있었다.
그래서 “이분 탐색으로 풀 수 있지 않을까?” 라는 생각이 들었는데,
문제는 어떤 로직으로 이분 탐색을 적용할 것인가였다.
이분탐색을 어떻게 적용할까
예시로 주어진 지형을 가지고
모든 목표 높이 H에 대해 비용을 직접 계산해보면
흥미롭게도 비용이 V자 모양으로 변한다는 걸 알 수 있었다.
즉,
- •
목표 높이를 너무 낮게 잡으면
높은 칸들을 많이 깎아야 해서 비용 증가
- •
목표 높이를 너무 높게 잡으면
낮은 칸들을 많이 쌓아야 해서 비용 증가
- •
둘 사이 어딘가에서 비용이 최소
왜 V(접시) 모양이 되는가?
핵심은 간단하다.
H가 작을수록 → (H보다 높은 칸이 많아짐) → 제거 비용 커짐
즉,
너무 낮아도 비싸고, 너무 높아도 비싸다
그래서 H가 한쪽으로 치우칠수록 비용이 증가하고,
결국 가운데 어딘가에서 최소가 생긴다.
각 칸마다
- •
H보다 낮으면 → (H - 높이) × 추가비용 P
- •
H보다 높으면 → (높이 - H) × 제거비용 Q
이 작업이 모두 선형이기 때문에 각 칸은 “V자” 형태 비용을 만들고 전체 비용은 이 V자들의 합 → 결국 볼록(convex) 이 된다.
그래서 최소값은 반드시 한 지점에만 존재한다.
따라서 나는 이분탐색을 아래와 같은 방식으로 짰다.
이 문제는 “mid가 정답인가?” 를 확인하는 방식이 아니다.
대신
mid 기준으로 → 어느 방향에 최소가 있는지를 판단
즉,
- •
cost(mid) <= cost(mid+1)→ 오른쪽으로 가면 비용이 오름
→ 최소는 mid 이하 범위
- •
cost(mid) > cost(mid+1)→ 왼쪽보다 오른쪽이 더 싸다
→ 최소는 mid+1 이상 범위
이 원리로 범위를 줄여 나가면 결국 left == right 에 도달하고 그 값이 최솟값을 만드는 H 가 된다.
최종 코드
public class Solution {
public int[][] land;
public int P,Q,n;
public long answer = Long.MAX_VALUE;
public long cost(long mid){
long temp = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(mid>land[i][j]){
temp += (mid-land[i][j])*P;
}
else{
temp += (land[i][j]-mid)*Q;
}
}
}
return temp;
}
public long solution(int[][] land, int P, int Q) {
n = land.length;
this.land = land;
this.P = P;
this.Q = Q;
long right = 0;
long left = Long.MAX_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
right = Math.max(right, land[i][j]);
left = Math.min(left, land[i][j]);
}
}
while(left < right){
long mid = (left + right) / 2;
long c1 = cost(mid);
long c2 = cost(mid + 1);
if(c1 <= c2) {
right = mid;
} else {
left = mid + 1;
}
}
return cost(right);
}
}