프로그래머스 문제 - 지형 편집

프로그래머스 지형 편집 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

이 문제는 그림을 보고 읽는 것이 알아보기 쉽습니다.

문제 풀이

정해진 높이의 위의 높이를 깎고 아래의 빈 공간을 채우며 평지를 만들 때 최소한의 비용이 드는 구간을 찾아야합니다.

처음 문제를 보자마자 최대 90000개의 블록을 하나하나 검색하기에는 무조건 시간초과가 나오는 것을 깨달았습니다.
그래서 제일 낮은 높이부터 다음 높이로 한 단계씩 넘어가면서 지형을 자르고 계산하는 방법이 시간복잡도도 짧고 좋은 방법이라 생각하였습니다.

일단 블록의 높이를 1차원 배열에 나열 후 낮은 높이에서부터 계산을 위해 sort를 진행하여 오름차순으로 만들어줍니다.

같은 높이의 블록이 여러 개 있을 수 있으니 전에 계산했던 높이와 그 높이보다 적은 블록들의 수를 저장해주며 for문을 돌려줍니다.
만약
4, 4, 3
3, 2, 2
2, 1, 0
처럼 지형이 있고 P=5, Q=3일 경우
[0, 1, 2, 2, 2, 3, 3, 4, 4]라는 1차원 배열로 나열될 것이며
앞에서부터 차레대로 높이를 보며 계산해줍니다.
높이를 0으로 맞출 경우 현재까지의 높이보다 작은 블록은 0이며 지울 블록은 모든 값을 더한 21입니다.
더했을 때 필요한 높이는 0*0 이므로 높이보다 낮은 블록들의 수와 필요한 높이를 비교하여 블록을 추가하는데 필요한 비용 P를 곱해줍니다.
지웠을 때 필요한 높이는 0*9 이므로 높이보다 높은 블록들의 수와 필요한 높이를 비교하여 블록을 지우는데 필요한 비용 Q를 곱해줍니다.
그러므로 높이가 0일때 필요한 비용은 0 + 63으로 63이라는 비용이 나옵니다.

즉, (블록을 더하여 높이를 맞추는데 필요한 블록들의 수 - 높이보다 낮은 블록들의 수) * 블록을 추가하는데 필요한 비용 + (블록을 빼서 높이를 맞추는데 필요한 블록들의 수 - 높이보다 높은 블록들의 수) * 블록을 제거하는데 필요한 비용이라는 식이 나옵니다.

이런 식으로 마지막까지 계산하여 최솟값을 구하면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include<vector>
using namespace std;

long long solution(vector<vector<int> > land, int P, int Q) {
    long long answer = LLONG_MAX;
    vector<long long> landNum;
    long long sum = 0;
    int n = land.size();
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            landNum.push_back(land[i][j]);
            sum += land[i][j];
            //rightSum.second++;
            //rightSum.first += land[i][j] * Q;
        }
    }
    sort(landNum.begin(), landNum.end());

    long long lastLand = -1;    //이전에 계산한 층수
    long long blocks = 0;    //이전에 계산한 블록들의 수
    for(int i = 0; i < landNum.size(); i++)
    {
        if(lastLand != landNum[i])
        {
            //(landNum[i] * i) : 쌓을 높이를 맞출 시 존재햐아하는 블록의 수
            long long left = (landNum[i] * i) - blocks;
            //(landNum[i] * (landNum.size() - i)) -> 블록을 빼서 높이를 맞출 시 존재햐아하는 블록의 수
            //sum - blocks -> 빼는 블록들의 수
            long long right = sum - blocks - (landNum[i] * (landNum.size() - i));
            long long value  = left * P + right * Q;
            if(answer > value)
                answer = value;
            //다음 높이 값 저장
            lastLand = landNum[i];
        }
        //왼쪽 블록들의 수 저장
        blocks += landNum[i];
    }
    
    return answer;
}

출저

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