[프래그래머스] 매출 하락 최소화 - 브루트포스부터 DP까지

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

프로그래머스

 

오늘 포스팅해볼 문제는 프로그래머스의 [매출 하락 최소화]다.

 

1. 첫 번째 접근 - 브루트포스

 

나는 이 문제를 풀기 위해 브루트포스 방식으로 먼저 작성해보았다.

브루트포스 방식은 매우 직관적이다.

팀 내에서 1명씩 선택하여 sale을 더했을 때, 총합이 가장 작은 경우를 정답으로 출력한다.

 

하지만 이 방식은 제출 시 시간 초과 빔을 맞게 되는데, 최대 직원 수가 300,000이기 때문에

 

1번 팀장의 팀원들 - 2 3 4 ... 100,000

2번 팀장의 팀원들 - 100,001, ..., 200,000

 

이런 트리만 있어도 약 10,000,000,000, 즉 100억 가지 조합이 발생한다.

 

2. 두 번째 접근 - DP

그래서 더 효율적인 알고리즘을 찾기 위해 고민했고, 그 결과 같은 연산이 반복되는 것을 발견할 수 있었다.

예를 들자면, 팀 C에서 5번이 선택됐을 때나 4번이 선택됐을 때나 팀 D를 똑같이 순회해야 했고,

그 결과는 똑같이 D 6번이 최소 비용이었다.

출처: 프로그래머스 매출 하락 최소화 문제

따라서 무언가를 저장해야 한다는 것을 알 수 있었고, 나는 각 직원 id에 대해, id가 참석하는 경우의 최소 비용과, id의 참석 여부와 상관없이 서브트리 조건을 만족하는 최소 비용 2가지를 저장하기로 했다.

 

현재 직원이 참석하는 경우에는 현재 직원의 매출액을 더하고, 자식 서브트리들은 각각 최소 비용을 선택하면 된다.
반대로 현재 직원이 참석하지 않는 경우에는 직속 팀원 중 적어도 한 명은 참석해야 한다. 따라서 모든 자식 서브트리의 최소 비용을 더한 뒤, 그중 한 자식을 참석 상태로 바꾸는 데 필요한 추가 비용이 가장 작은 값을 더해준다.

 

이를 postorder 방식으로 순회하면 자식 노드의 DP 값을 먼저 계산한 뒤 부모 노드의 DP 값을 계산할 수 있다. 각 노드에서는 직속 자식들만 순회하면 되고, 전체 트리에서 부모-자식 간선의 수는 N-1개이므로 전체 시간복잡도는 O(N)이 된다.

 

즉, 이 문제는 트리 순회 + DP가 섞여 있는 응용 문제였다.

 

나는 처음에 이를 풀기 위해 Employee 구조체를 정의했다. 구조체를 사용하면 직원의 정보와 팀원 목록을 한 객체 안에 묶을 수 있어 직관적이지만, 내가 처음 작성한 방식에서는 Employee 객체를 포인터로 연결해야 했고, 이 과정에서 new/delete를 직접 관리해야 했다. 또한 함수 인자로 포인터나 참조를 계속 전달해야 해서 코드가 복잡해졌다.

struct Employee {
    Employee(int id, int sale) {
        this->id = id;
        isLeader = false;
        this->sale = sale;
        minSalesSumIncludingMe = INF;
        minSalesSumOfTeam = INF;
    }
    int id;
    bool isLeader;
    int sale;
    int minSalesSumIncludingMe; // 내가 포함됐을 때 최소 비용
    int minSalesSumOfTeam; // 내가 포함되든 아니든 최소 비용
    vector<Employee*> members;
};

 

3. 개선

그래서 다른 사람들의 풀이를 참고하며 구조체를 없애고, 직원 id를 인덱스로 사용하는 방식으로 개선했다. 직속 팀원 정보는 2차원 벡터에 저장하고, DP 값은 array를 원소로 가지는 벡터에 저장했다.

vector<vector<int>> employees(n + 1);
// dp[id][0]: id를 루트로 하는 서브트리에서 팀 조건을 모두 만족하는 최소 비용
// dp[id][1]: id가 선택됐을 때, id를 루트로 하는 서브트리에서 팀 조건을 모두 만족하는 최소 비용
vector<array<int, 2>> dp(n + 1, { 0, INF });

 

코드 개선 후, 같은 DP여도 어떤 자료 구조를 사용하는지에 따라 코드의 형태가 많이 달라진다는 것을 체감했다.

특히나, 자식을 표시할 때, 복사나 포인터가 아닌 id로 저장하는 방식이 코드가 훨씬 단순해졌다. 앞으로 트리 문제를 풀 때에도 유용하게 사용할 수 있을 것 같다.

 

4. 최종 코드

#include <vector>
#include <array>
#include <algorithm>
#include <limits>

using namespace std;

constexpr int INF = numeric_limits<int>::max();

// dp를 기록하는 함수
// 재귀 호출을 통해 트리를 postOrder 순회
void recordMinSales(int cur, const vector<vector<int>>& employees, const vector<int>& sales, vector<array<int, 2>>& dp) {
    const vector<int>& childs = employees[cur];

    // leaf이면 선택됐을 때 비용은 자신의 sales, 선택되지 않아도 팀 조건은 없음
    if (childs.empty()) {
        dp[cur][0] = 0;
        dp[cur][1] = sales[cur - 1];
        return;
    }

    // 자식들의 dp부터 초기화
    for (int child: childs) {
        if ( dp[child][1] == INF) {
            recordMinSales(child, employees, sales, dp); // 재귀 호출
        }
    }

    // cur이 선택된 경우
    dp[cur][1] = sales[cur - 1];

    for (int child : childs) {
        dp[cur][1] += dp[child][0];
    }

    // cur이 선택되지 않은 경우
    // 직속 팀원 중 적어도 1명은 선택해야 함
    int notSelected = 0;
    int minDiff = INF;

    for (int child: childs) {
        dp[cur][0] += dp[child][0];
        minDiff = min(minDiff, dp[child][1] - dp[child][0]);
    }
    dp[cur][0] += minDiff;

    // cur이 선택된 경우와 선택되지 않은 경우 중 최소
    dp[cur][0] = min(dp[cur][1], dp[cur][0]);

    return;
}

int solution(vector<int> sales, vector<vector<int>> links) {
    int n = sales.size();

    vector<vector<int>> employees(n + 1);
    // dp[id][0]: id를 루트로 하는 서브트리에서 팀 조건을 모두 만족하는 최소 비용
    // dp[id][1]: id가 선택됐을 때, id를 루트로 하는 서브트리에서 팀 조건을 모두 만족하는 최소 비용
    vector<array<int, 2>> dp(n + 1, { 0, INF });

    for (const vector<int>& link : links) {
        int leaderNum = link[0];
        int memberNum = link[1];

        employees[leaderNum].push_back(memberNum);
    }

    recordMinSales(1, employees, sales, dp);
  
    return dp[1][0];
}