[알고리즘] 5번째 알고리즘 문제 풀기

[ujkkk]

📝 Description

무엇을?

• 5번째 알고리즘 문제 풀기

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[ujkkk]

1052. Grumpy Bookstore Owner

class Solution { public static int maxSatisfied(int[] customers, int[] grumpy, int minutes) { int start =0, end =0; int maxBenefit = 0;

    // 초기 세팅
    for(int i=0; i < minutes; i++){
        maxBenefit += grumpy[end] == 1 ? customers[end] : 0;
        end++;
    }

    int benefit = maxBenefit;
    while(end < customers.length){
        // start의 비용 빼기
        benefit -= grumpy[start] == 1 ? customers[start] : 0;
        // end 비용 추가
        benefit += grumpy[end] == 1 ? customers[end] : 0;

        if(benefit > maxBenefit){
            maxBenefit = benefit;
        }
        start++; end++;
    }

    int total = 0;
    for(int i=0; i<customers.length; i++){
        total += grumpy[i] == 0 ? customers[i] : 0;
    }
    return total + maxBenefit;
}

}

[ujkkk]

188. Best Time to Buy and Sell Stock IV (못품)

class Solution {
     public static int maxProfit(int k, int[] prices) {
        if(prices.length == 1){
            return 0;
        }

        int [][][] dp = new int[k+1][2][prices.length];
        for(int i=0; i<prices.length; i++){
            dp[0][0][i] = -prices[i];
        }

        for(int i=0; i<=k; i++){
            dp[i][0][0] = -prices[0];
        }

        for(int j=1; j<=k; j++){
            for(int i=1; i<prices.length; i++){
                // 유지하거나 사거나 - 살 때 거래 횟수 증가
                dp[j][0][i] = Math.max(dp[j-1][0][i-1] , dp[j][1][i-1] - prices[i]);
                // 유지하거나 팔거나
                dp[j][1][i] = Math.max(dp[j][1][i-1], dp[j][0][i-1] + prices[i]);
            }
        }

        int max = 0;
        for(int i=0; i<=k; i++){
            max = Math.max(max, dp[i][1][prices.length-1]);
        }
        return max > 0 ? max : 0;
    }
}