[C/C++] Lv4 프로그래머스 - 지형 편집

programmers.co.kr/learn/courses/30/lessons/12984

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

- 접근법

이 문제에서 만들 수 있는 테스트케이스(TC)에서 각 높이를 기준으로 블럭을 제거하고 새로 쌓아 얻은 추가비용들을 그래프화 시켜보면 유형은 크게 3가지로 나눌 수 있다.(x축이 높이, y축이 cost)

첫번째 경우처럼 최대높이에서 최소cost가 나오는 경우 (값이 계속 감소)

두번째 경우처럼 높이 0 에서 최소cost가 나오는 경우 (값이 계속 증가)

세번째 경우처럼 일정 높이까지는 값이 감소하다가 일정 높이부터 다시 값이 증가하는 경우

 

값이 증가하다가 감소하는 경우는 나오지않는 이유는 (블럭은 아래층부터 쌓여있기 때문이다.)

 

따라서 이 문제는 그래프의 값이 최솟값인 부분을 찾는 경우이므로

포괄해서 생각해보면 변곡점을 찾으면 될것이다.

 

그렇기 때문에 이분탐색으로 (0~주어진 값의 최대높이) 에서 mid를 선택하고 mid-1, mid+1의 경우의 값을 같이 구해주어서 f(mid-1), f(mid), f(mid+1)의 값을 토대로 현재 위치가 감소하고있는 부분인지, 증가하고 있는 부분인지.

아니면 변곡점인 부분인지(f(mid-1)>=f(mid) 이고 f(mid)<=f(mid+1)) 판단하면 된다.

 

만약 감소하고 있는 부분이라면 이분탐색을 right로 보내고

(그래프 1의 경우 right로 계속 보내면 결국 최대 높이에서 수렴할 것이다.)

증가하고 있는 부분이라면 이분탐색을 left로 보내면 된다!

(그래프 2의 경우 left로 계속 보내다보면 최소 높이에서 수렴할 것이다.)

 

정확성 테스트

효율성 테스트

 

 

---

- 소스코드

#include<vector>
#include<math.h>
#include<iostream>
using namespace std;
#define MAXI(A,B) A>B ? A : B
int board[302][302];
int N;
int maxi_h=0,mini_h=1000000001;
void init(vector<vector<int> > land) {
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            board[i][j]=land[i][j];
            maxi_h=MAXI(maxi_h,board[i][j]);
        }
    }
}
long long details(long long temp,int P,int Q) {
    long long num=0;
    if(temp<0) {
        num=(long long)(temp*P*(-1));
    }
    else {
        num=(long long)(temp*Q);
    }
    return num;
}
long long calc(int height,int P,int Q) {
    long long sum_left=0,sum_mid=0,sum_right=0;
    long long temp1,temp2,temp3;
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            temp1=board[i][j]-(height-1); // left
            temp2=temp1-1; // mid
            temp3=temp1-2; // right
            sum_left+=details(temp1,P,Q);
            sum_mid+=details(temp2,P,Q);
            sum_right+=details(temp3,P,Q);
        }
    }
    if(sum_left>=sum_mid && sum_mid<=sum_right) return sum_mid; // 변곡점
    if(sum_left>=sum_mid && sum_mid>=sum_right) return (-2); // 감소 기울기
    if(sum_left<=sum_mid && sum_mid<=sum_right) return (-1); // 증가 기울기
}
long long solution(vector<vector<int> > land, int P, int Q) {
    long long answer;
    long long mid_c=0;
    int start,end,mid;
    long long left,right;
    N=land.size();
    init(land);
    start=0;
    end=maxi_h;
    while(start<=end) {
        mid=(start+end)/2;
        mid_c=calc(mid,P,Q);
        if(mid_c==-2) {
            start=mid+1;
        }
        else if(mid_c==-1) {
            end=mid-1;
        }
        else {
            answer=mid_c;
            break;
        }
    }
    return answer;
}