Summer/Winter Coding - # 11. 지형 편집

코딩 테스트 연습 - 지형 편집 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

11. 지형 편집

문제 설명

XX 게임에서는 지형 편집 기능을 이용하여 플레이어가 직접 게임 속 지형을 수정할 수 있습니다. 이 게임에서는 1 x 1 x 1 크기의 정육면체 블록을 쌓아 게임 속 지형을 표현합니다. 이때, 블록이 공중에 떠 있거나, 블록 하나가 여러 개의 칸에 걸쳐 놓일 수는 없습니다. 따라서 지형을 편집하기 위해서는 각 칸의 제일 위에 블록 1개를 새로 추가하거나, 제일 위에 있는 블록 한 개를 삭제하는 방식으로 지형을 수정해야 합니다. 이때, 블록 한 개를 새로 추가하거나 삭제하기 위해서는 게임머니를 사용해야 하므로 몇 개의 블록을 추가하고 삭제할지 신중한 선택이 필요합니다.

이 게임을 즐기던 한 플레이어는 N x N 크기의 지역에 자신만의 별장을 만들고 싶어 졌습니다. 이를 위해서는 울퉁불퉁한 지형의 모든 칸의 높이가 같아지도록 만들어야 합니다. 이때, 블록 한 개를 추가하려면 P의 비용이, 제거하려면 Q의 비용이 들게 됩니다.
다음은 블록 한 개를 추가할 때 5의 비용이, 제거할 때 3의 비용이 드는 경우, 3 x 3 넓이의 모든 칸의 블록 높이가 같아지도록 만드는 예시입니다.

위 그림과 같이 지형 블록이 놓여 있는 경우 모든 칸의 높이가 3으로 같아지도록 한다면 다음과 같은 모양이 됩니다.

이를 위해서는 3보다 높은 칸의 블록 2개를 제거하고, 3보다 낮은 칸에 총 8개의 블록을 추가해야 하며, 2 x 3 + 8 x 5 = 46의 비용이 들게 됩니다.

그러나 아래 그림과 같이 모든 칸의 높이가 2로 같아지도록 할 때는 6개의 블록을 제거하고, 3개의 블록을 추가하면 6 x 3 + 3 x 5 = 33의 비용이 들게 되며, 이때가 최소비용이 됩니다.

현재 지형의 상태를 나타내는 배열 land와 블록 한 개를 추가하는 데 필요한 비용 P, 블록 한 개를 제거하는 데 필요한 비용 Q가 매개변수로 주어질 때, 모든 칸에 쌓여있는 블록의 높이가 같아지도록 하는 데 필요한 비용의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• land는 N x N 크기의 2차원 배열이며, N의 범위는 1 ≤ N ≤ 300입니다.
• land의 각 원소는 각 칸에 놓여 있는 블록의 수를 나타내며, 0 이상 10억 이하의 정수입니다.
• 각 칸에 블록 하나를 추가하는 데는 P, 제거하는 데는 Q의 비용이 들며, P, Q의 범위는 1 ≤ P, Q ≤ 100인 자연수입니다.

---

입출력 예landPQresult

[[1, 2], [2, 3]]	3	2	5
[[4, 4, 3], [3, 2, 2], [ 2, 1, 0 ]]	5	3	33

입출력 예 설명

입출력 예 #1

• 모든 땅의 높이를 1로 맞추는 데는 블록 4개를 제거해야 하므로 8의 비용이 듭니다.
• 모든 땅의 높이를 2로 맞추는 데는 블록 1개를 추가하고 블록 1개를 제거해야 하므로 5의 비용이 듭니다.
• 모든 땅의 높이를 3으로 맞추는 데는 블록 4개를 추가해야 하므로 12의 비용이 듭니다.

따라서 최소 비용은 5이므로 5를 return 합니다.

입출력 예 #2
문제의 예시와 같으며 최소 비용은 33입니다.

 

---

[문제 해설]

 

1. 일일히 인덱스를 순회하면 같은 층을 맞추고 그 층이 최소가 되는 비용인지 체크하기는 어렵다.

2. 그리디하게 문제 풀기가 어려우니 그럴 때는 완전 탐색으로 푸는 것도 좋은 방법이다.

3. 그럼 완전탐색을 시작해보자!!

4. 우선 계산을 쉽게 하기 위해 층을 미리 모두 제거해서 0층으로 만들어보자 => 층 모든 지형을 제거했으므로 그만큼 비용 계산

5. 그 다음 가장 낮은 층을 기준으로 비용을 계산해서 시작비용으로 시작할 것이다. 왜 그러냐면 그건 나중에 설명

6. 일단 주어지는 land를 선형의 land리스트로 바꾼 다음 sort 한다. (인덱스 순으로 층의 높이가 정렬 된다.)

7. 0층 또는 그다음 낮은 층 둘 중 하나의 최소비용이 저장돼있는 상태다.

8. 랜드의 층수를 sort 했으므로 index가 높아짐에 따라 층의 높이 높아진다.

9. 이때 우리는 층의 높이가 달라질 때마다 층이 높아지는 쪽으로 비용을 재계산한다. (고로 인덱스 1부터 시작한다)

9-1. 이것이 우리가 가장 낮은 층의 비용 계산을 먼저 한 이유이다. 층의 높이를 비교하면서 높이가 다르면 높은 쪽으로 비용을 재계산하면서 가장 작은 비용을 기억하게 할 것이다 (인덱스 끝 즉, 최대 높이층까지)

9-2. 다시 설명하면, 초기 제거하는 비용을 모두 써서 0층을 만들고, 그다음 바로 높은 층을 계산해서 둘 중 하나는 가장 낮은 층으로 제거 비용만 써서 계산한 최소 비용이 된다.

=> 제거 비용은 이미 다 계산했으므로 층을 순회하면서 설치 비용만 고려하면서 최소 비용을 찾는 완전 탐색을 구현한 것.

=> 층이 달라지면 미리 했던 제거 비용을 취소하고, 설치 비용을 추가하는 식으로 계산하면서 최소비용을 찾는 것,

10. 말로 이렇게 설명하기도 어렵운데 거기다 실제 구현도 잘 이해가 안 될 수 있다. 코드를 보고 고심하기 바람! (주석 참고)

 

---

[코드]

def solution(land, P, Q):
    newland = []
    for la in land:
        newland.extend(la)

    newland.sort()
 
    # 0층으로 만드는 비용
    answer = sum(newland) * Q
    # 첫 번째 인덱스 층으로 기준을 잡았을때의 비용
    # 순회할 때 높이의 차이가 생길 경우 계산을 할거기 때문에 첫 번째를 미리 계산 하는 것
    candi = (sum(newland) - newland[0] * len(newland)) * Q
    
    answer = min(answer, candi)

    for idx in range(1, len(newland)):
    	# 층이 다름
        if newland[idx - 1] != newland[idx]:
        	# 층이 다른만큼 계산, 앞에는 설치 비용 계산, 뒤에는 앞서 이미 제거 비용을 취소해야하므로 그것을 계산한 것
            candi += ((newland[idx] - newland[idx - 1]) * P * idx) - ((newland[idx] - newland[idx - 1]) * Q * (
                        len(newland) - idx))

            answer = min(answer, candi)

    return answer

---

후기

 

문제를 풀면서 그리디 하게 풀기 어려울 거 같으면 완전 탐색을 고려!

완전 탐색을 고려했는데 너무 경우의 수가 많은데 마침 그래프 문제면

bfs, dfs를 고려

bfs, dfs로 순회를 너무 많이 하는데 그럼 dp를 고려..

대충 이런 나만의 생각의 흐름을 가져야 시간 내에 문제를 풀 수 있는 듯하다.