프로그래머스 - 지형 편집

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

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

 

이분탐색을 써야 된다는 것을 알았다. 하지만 범위를 어떻게 줄여나가야 될 지 감이 안잡혔다.

 

그래서 ydeer.tistory.com/78 이 분꺼를 보고 방법을 익혔다.

 

 

생각보다 좀 어려운 문제였다.

 

 

 

#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;

ll getVal(const vector<vector<int>>& land, ll level, int Q, int P) {
    ll ret = 0;
    for(int i = 0; i < land.size(); i++) {
        for(int j = 0; j < land[i].size(); j++) {
            if(land[i][j] > level) {
                ret += (land[i][j] - level) * Q;
            } else if(land[i][j] < level) {
                ret += (level - land[i][j]) * P;
            }
        }
    }
    return ret;
}

long long solution(vector<vector<int> > land, int P, int Q) {
    long long answer = 0;
    
    ll low = 0;
    ll high = 1000000000;
    ll mid, result;
    
    while(low < high) {
        mid = (low + high) / 2;

        
        ll sum1 = getVal(land, mid, Q, P);
        ll sum2 = getVal(land, mid + 1, Q, P);
        
        if(sum1 == sum2) {
            break;
        } else if(sum1 < sum2) {
            high = mid;
        } else {
            low = mid + 1;
        }
        
    }
    
    answer = getVal(land, (low + high) / 2, Q, P);
    
    
    return answer;
}

 

 

 

개발 환경 : vscode

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