leetcode 1478 - Allocate Mailboxes

https://leetcode.com/problems/allocate-mailboxes/

풀이

우체통이 한 개 있는 경우만 먼저 생각해보면 집을 정렬했을 때 중앙값에 해당하는 위치에 두는 것이 가장 최적이다.

우체통이 두 개가 있는 경우에 최적은 임의의 집을 기준으로 왼쪽에 위치한 집은 왼쪽 우체통에, 오른쪽에 위치한 집은 오른쪽 우체통에 짝짓는 것이 최적이다. 

 

 

이 두 가지를 기반으로 아래와 같이 점화식을 세울 수 있다.

d[i][j] = i개의 우체통을 1 ~ j 집까지 커버하도록 설치하는 최소 거리

결국 맨 오른쪽에 위치시킬 우체통은 맨 오른쪽에 위치한 집들을 커버할 것이기 때문에 어디까지 커버할지 l을 순회하면서 최적의 값을 찾으면 된다. 

 

 

코드

class Solution {
public:
    int minDistance(vector<int>& houses, int k) {
        vector<vector<int>> d(k, vector<int>(houses.size()));
        vector<vector<int>> distance(houses.size(), vector<int>(houses.size()));
        
        sort(houses.begin(), houses.end());
 
        for(int i = 0; i < houses.size(); i++) {
            for(int j = i; j < houses.size(); j++) {
                for(int l = i; l <= j; l++) {
                    distance[i][j] += abs(houses[(i+j)/2] - houses[l]);
                }
            }
            
            d[0][i] = distance[0][i];
        }
        
        for(int i = 1; i < k; i++) {
            for(int j = 0; j < houses.size(); j++) {
                d[i][j] = 123456789;
                for(int l = 0; l < j; l++) {
                    d[i][j] = min(d[i][j], d[i-1][l] + distance[l+1][j]);
                }
            }
        }
        
        return d[k-1][houses.size()-1];
    }
};