프로그래머스 지형 편집 자바 풀이

문제 링크

문제 풀이 시간 : 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)
cost(mid) > cost(mid+1)

이 원리로 범위를 줄여 나가면 결국 left == right 에 도달하고 그 값이 최솟값을 만드는 H 가 된다.

최종 코드

java

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);
    }
}

지형 편집

문제 풀이 시간 : 38분

문제 요약

문제 풀이

이분탐색을 어떻게 적용할까

왜 V(접시) 모양이 되는가?

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기