[프로그래머스 C#] Lv.4 지형 편집

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 2차원 영역의 층을 같은 높이로 맞추는 데에 드는 최소 비용을 구하는 문제

- 같은 높이로 맞추기 위해 가능한 건, 층을 추가하거나 삭제하는 것 뿐 (이동X)

 -> 층을 추가하는 비용과 삭제하는 비용은 따로 주어짐

 

중복 연산 최적화 아이디어

- 주어진 2차원 배열을 리스트에 저장해 오름차순으로 정렬 ( 계단 형태가 됨 )

- 정렬된 리스트를 0번 인덱스부터 순회해 가장 낮은 층부터 높은 층의 방향으로 만들어나감

- 현재 만들려는 층에 대한 연산은 이전에 만들었던 층의 결과에 추가, 삭제해 중복 연산을 최소화

 -> 이전 층보다 높아지면서 제거했던 블록을 복구해야 함 (제거한 비용을 돌려받기)

 -> 이전 층보다 높아지면서 층을 맞추기 위해 블록을 추가해야 함

 ( 위 두개의 연산의 제거하거나 추가하는 영역은 무조건 직사각형 영역이 됨 )

 

+ 주어진 문제의 특성 상 만들려는 층에 따른 비용 그래프는 2차원 그래프 형태를 띄므로 가장 낮은 층에서부터 높은 층으로 탐색을 이어갈 때 최소 비용이 갱신이 되지 않는다면, 층에 따라 탐색되는 비용은 점점 높아지므로 탐색할 필요가 없음

 

+ 층의 높이의 최대 값은 10억으로 int 자료형의 범위를 벗어나기 쉬우므로 long 자료형으로 연산하게 되는데, 형 변환이 되지 않아 값이 잘못되는 경우를 유의해야 함

 

주석 참조

    using System;
    using System.Collections.Generic;
    using System.Linq;

    public class Solution
    {
        public long solution(int[,] land, int p, int q)
        {
            long minCost, currCost; // 최소비용. 현재비용
            var list = new List<int>(); // 각 칸의 블록 개수 (층 개수)

            foreach (int i in land)
                list.Add(i);

            list.Sort(); // 오름차순 정렬

            // 가장 낮은 층으로 만드는 비용 (가장 낮은 층을 기준으로 모든 층 제거)
            long subNum = (long)list[0] * list.Count;
            currCost = (list.Sum(x => (long)x) - subNum) * q;
            minCost = currCost;

            for (int i = 1; i < list.Count; i++)
            {
                // 같은 층에 대해 다루게 되므로 pass
                if (list[i - 1] == list[i])
                    continue;

                long addFloor = list[i] - list[i - 1]; ; // 층 증가 수

                // 만들려는 층이 변경됨에 따라 제거했던 층을 취소
                currCost -= addFloor * (list.Count - i) * q;

                // 만들려는 층이 변경됨에 따라 추가되는 층을 추가
                currCost += addFloor * i * p;
                
                // 최소 비용이 갱신되지 않는다면
                if (minCost < currCost)
                    break;

                minCost = currCost;
            }

            return minCost;
        }
    }