[LeetCode] 3562. Maximum Profit from Trading Stocks with Discounts

https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts/description/?envType=daily-question&envId=2025-12-16

LeetCode - Maximum Profit from Trading Stocks with Discounts

문제 유형: 다이나믹 프로그래밍, 트리, 그래프

문제 난이도: Hard

 

문제

You are given an integer n, representing the number of employees in a company. Each employee is assigned a unique ID from 1 to n, and employee 1 is the CEO. You are given two 1-based integer arrays, present and future, each of length n, where:

• present[i] represents the current price at which the ith employee can buy a stock today.
• future[i] represents the expected price at which the ith employee can sell the stock tomorrow.

The company's hierarchy is represented by a 2D integer array hierarchy, where hierarchy[i] = [ui, vi] means that employee ui is the direct boss of employee vi.

Additionally, you have an integer budget representing the total funds available for investment.

However, the company has a discount policy: if an employee's direct boss purchases their own stock, then the employee can buy their stock at half the original price (floor(present[v] / 2)).

Return the maximum profit that can be achieved without exceeding the given budget.

Note:

• You may buy each stock at most once.
• You cannot use any profit earned from future stock prices to fund additional investments and must buy only from budget.

n명의 사원들이 있고, 사원번호는 1~n번으로 주어진다.

1번이 CEO이다.

 

1-based 정수배열 present, future가 주어진다. present[i]는 i번째 사원이 주식을 사는 비용, future[i]는 i번째 사원이 주식을 팔 때의 비용이다.

회사의 조직도는 [u_i, v_i]꼴로 주어지며, u_i가 v_i의 직속상사라는 뜻이다.

만약 자신의 직속상사가 주식을 산다면, 그 아래 사원은 반값(소수점 버림)으로 살 수 있다.

최대 이익을 구하시오.

단, 사원들은 각각 한번씩만 사고팔 수 있으며, 다른 사람이 사고판 돈으로 추가로 살 수는 없습니다.

 

풀이

https://leetcode.com/problems/maximum-profit-from-trading-stocks-with-discounts/solutions/7416833/tree-dp-knapsack-max-profit-with-budget-mw1iy/?envType=daily-question&envId=2025-12-16

를 참고..

매우 어려운 Tree DP 문제이다.

 

우선, 1-based를 0-based로 바꾼다.

 

dp[u][부모가 샀는지여부][사용예산]으로 dp테이블을 정의한다.

 

우선, 자식들의 케이스들을 먼저 계산한다(postorder)

 

그 뒤 상사의 구매여부 두 가지 케이스 모두 고려해서,

이번 노드를 사는 경우:

  자식들에게 예산 b로 얻을 수 있는 최대 이익을 구한다.
  dp[v][0][b]는 아래 자식이 b에서 사는 경우를 말하는데, base라는 이전에 처리한 자식들 값을 기반으로 하위 배낭문제 케이스들을 병합하는 것이다.

  이후에, 결과를 반영한다.

 

  price가 이번 예산보다 작거나 같다면, 새로 사는 것을 시도할 수 있다.

새로운 최대 이익을 구한다. 여기서는 dp[v][1][b]를 기반으로, 즉 u에서 구매했으니, 그 자식인 v는 반값에 살 수 있는 것을 반영하여 배낭들을 병합한다.

 

최종적으로 결과를 dp테이블에 업데이트한다.

 

dp[0][0]에서 가장 큰 값을 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();
class Solution {
public:
    const int INF = 1e9;
    int n, B;
    vector<int> present, future;
    vector<vector<int>> adj;
    // dp[u][parentbought][budget]
    vector<vector<vector<int>>> dp;
    void dfs(int u) {
        for(int v : adj[u]) {
            dfs(v);
        }

        for(int parentBought = 0; parentBought <= 1; parentBought++) {
            int price = parentBought? present[u] / 2 : present[u];
            int profit = future[u] - price;

            vector<int> curr(B+1, 0);

			// u를 안사는 경우
            vector<int> base(B+1, 0);
            for(int v : adj[u]) {
                vector<int> next(B+1, 0);
                for(int b1 = 0; b1 <= B; b1++) {
                    for(int b2 = 0; b1 + b2 <= B; b2++) {
                        next[b1 + b2] = max(next[b1 + b2], base[b1] + dp[v][0][b2]);
                    }
                }
                base.swap(next);
            }

            for(int b = 0; b <= B; b++) {
                curr[b] = base[b];
            }

			// u를 사는경우
            if(price <= B) {
                vector<int> baseBuy(B+1, 0);
                for(int v : adj[u]) {
                    vector<int> next(B+1, 0);
                    for(int b1 = 0; b1 <= B; b1++) {
                        for(int b2 = 0; b1 + b2 <= B; b2++) {
                            next[b1 + b2] = max(next[b1 + b2], baseBuy[b1] + dp[v][1][b2]);
                        }
                    }
                    baseBuy.swap(next);
                }
                
                for(int b = price; b <= B; b++) {
                    curr[b] = max(curr[b], baseBuy[b-price] + profit);
                }
            }

            dp[u][parentBought] = move(curr);
        }
    }
    int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {
        this -> n = n;
        this -> B = budget;
        this -> present = present;
        this -> future = future;
        adj.resize(n);
        for(auto &h : hierarchy) {
            adj[h[0]-1].emplace_back(h[1]-1);
        }

        dp.resize(n, vector<vector<int>>(2, vector<int>(B+1)));

        dfs(0);

        int ans = 0;
        for(int b = 0; b <= B; b++) {
            ans = max(ans, dp[0][0][b]);
        }

        return ans;
    }
};