[프로그래머스][level4] 지형 편집 (C++)

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

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

 

 

[난이도] level4
[유형] 누적합

[풀이]
N*N의 최대가 300*300이기 때문에 모든 땅을 같은 높이로 맞춰보는 방법은 (300*300)^2 연산으로
O(N^4)의 시간복잡도를 필요로 하기 때문에 사용이 불가능합니다.

하지만 누적합 배열을 이용하면 쉽게 O(N^2) 으로 해결이 가능합니다.

1) 우선 2차원 land 배열을 1차원 배열 arr[90001]로 옮긴 뒤 정렬해줍니다.
   이제 N=N*N으로 바꿔줍니다.

2) sum[90001] 배열을 누적합을 저장합니다.

3) 최적의 높이는 arr[1] 또는 arr[2] ... arr[N] 입니다. 이 이외의 높이로 맞추는 것은
   비용을 더 늘어나게 합니다.
   그러므로 arr[i]의 각 높이로 맞춰보면서 비용이 최소가 될때를 찾으면 됩니다.

   예를 들어 N=6이고 각 땅의 높이가 [3,3,4,4,5,7] 일때 아래 그림을 참고해봅시다.
   (N은 k^2 꼴이여야 하지만 편의상 6으로 설정하였습니다.)

   높이를 arr[3]=4로 맞추고 싶을 때, 좌측의 4보다 높이가 작은 땅은 파란색 영역 만큼
   높이를 증가시켜야 하고, 우측의 높이가 4보다 높은 땅은 초록색 영역만큼 높이를 줄여야 합니다.
   이는 누적합 배열 sum을 이용해 아래와 같이 계산이 가능합니다.

   좌측 파란색 영역 =
   [높이가 arr[i]이고 넓이가 i-1인 직사각형 : arr[i]*(i-1)]  -  [1~(i-1)까지 땅 높이의 합 : sum[i-1]]
    = arr[i]*(i-1)-sum[i-1]

   우측 초록색 영역 =
   [i~N까지 땅 높이의 합 : sum[N]-sum[i-1]] - [높이가 arr[i]이고 넓이가 (N-(i-1))인 직사각형 : arr[i]*(N-(i-1))]
    = arr[i]*(i-1)-sum[i-1]

   좌측 값만큼 블록을 추가해야 하므로 P를 곱하고, 우측 값만큼 블록을 제거해야 하므로 Q를 곱한 뒤
   두 값을 더하면 최종 비용을 구할 수 있습니다.

   i:1~N 의 모든 값에 대해 위의 연산은 해주며 최소 비용을 구하면 최종 답을 구할 수 있습니다.
   (arr[i]가 동일한 땅들은 가장 앞에 있는 땅만 계산해주면 됩니다.)

 

 

 

파라메트릭 서치를 이용한 풀이도 있지만 위의 풀이가 좀 더 직관적이고 코드가 간결합니다.

 

 

#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
ll arr[90001],sum[90001],ans=-1;
int N;
ll solution(vector<vector<int> > land, int P, int Q) {
    N=land.size();
    int idx=1;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            arr[idx++]=land[i][j];
    N*=N;
    sort(arr,arr+N+1);
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+arr[i]; 
    int cur=-1;
    for(int i=1;i<=N;i++){
        if(arr[i]==cur) continue;
        cur=arr[i];
        ll v=0;
        v+=(sum[N]-sum[i-1]-arr[i]*(N-(i-1)))*Q;
        v+=(arr[i]*(i-1)-sum[i-1])*P;
        if(ans==-1 || ans > v) ans=v;
    }
    return ans;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/지형_편집.cpp