C++로 풀어보는 주식 사고팔기 가장 좋은 시점 IV

주식 거래 문제를 함께 해결해 보겠습니다. 배열의 i번째 요소가 i일째 되는 날의 특정 주식 가격을 나타낸다고 가정해 봅시다. 우리는 최대 이익을 찾는 알고리즘을 설계해야 하며, 이때 최대 k번의 거래만 허용됩니다.

예를 들어 입력이 [3,2,6,4,0,3]이고 k = 2라면 출력은 7이 됩니다. 2일째 되는 날(가격이 2일 때)에 매수하고 3일째 되는 날(가격이 6일 때)에 매도하면 수익은 6 - 2 = 4입니다. 이후 5일째 되는 날(가격이 0일 때)에 다시 매수하고 6일째 되는 날(가격이 3일 때)에 매도하면 추가 수익은 3 - 0 = 3이 됩니다. 따라서 총 수익은 4 + 3 = 7입니다.

접근 방법: 메모이제이션 기반 동적 계획법

이 문제는 재귀 호출과 메모이제이션(memoization)을 결합한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 각 단계는 다음과 같습니다.

(N + 5) × (N + 5) × 2 크기의 3차원 배열 dp를 선언합니다.
dp 배열 전체를 -1로 초기화하는 pre() 메서드를 정의합니다. (-1은 '아직 계산되지 않음'을 의미합니다.)
배열 arr, 현재 인덱스 i, 총 일수 n, 남은 거래 횟수 k, 보유 상태 status를 인자로 받는 solve() 메서드를 정의합니다.

solve() 메서드의 동작 원리

i가 n과 같으면 모든 날을 확인한 것이므로 종료 조건을 검사합니다. 이때 status가 0이 아니면(아직 주식을 보유 중이면) 유효하지 않은 상태이므로 -100000을 반환하고, 그렇지 않으면 0을 반환합니다.
dp[i][k][status]의 값이 -1이 아니라면 이미 계산된 결과이므로 즉시 반환합니다.
ans := solve(arr, i + 1, n, k, status) — 아무 행동도 하지 않고 다음 날로 넘어가는 경우를 먼저 고려합니다.
status가 참이라면(현재 주식 보유 중): 매도하는 경우인 solve(arr, i + 1, n, k - 1, !status) + arr[i]와 비교하여 더 큰 값을 ans에 저장합니다.
status가 거짓이고 k > 0이라면(매수 가능): 매수하는 경우인 solve(arr, i + 1, n, k, !status) - arr[i]와 비교하여 더 큰 값을 ans에 저장합니다.
최종 결과를 dp[i][k][status]에 저장한 후 반환합니다.

메인 함수의 처리 과정

pre() 함수를 호출하여 dp 배열을 초기화합니다.
k가 prices 배열 크기의 절반 이상이라면 사실상 무제한으로 거래할 수 있으므로, 인접한 두 날의 가격 차이가 양수인 모든 구간의 차익을 단순히 더하는 그리디 방식으로 답을 구합니다.
그 외의 경우에는 solve(prices, 0, prices.size(), k, 0)를 호출하여 결과를 반환합니다.

구현 예시

다음 C++ 구현을 통해 개념을 더 명확하게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N = 1000;
lli dp[N + 5][N + 5][2];
class Solution {
    public:
    void pre(){
        for(lli i =0;i<=N;i++){
            for(lli j = 0;j<=N;j++){
                dp[i][j][1]=-1;
                dp[i][j][0]=-1;
            }
        }
    }
    lli solve(vector<int> &arr, lli i,lli n,lli k, lli status){
        if(i == n){
            if(status)return -100000;
            return 0;
        }
        if(dp[i][k][status]!=-1)return dp[i][k][status];
        lli ans = solve(arr, i+1,n,k,status);
        if(status){
            ans = max(ans,solve(arr,i+1,n,k-1,!status)+ arr[i]) ;
        } else {
            if(k>0){
                ans = max(ans,(lli)solve(arr,i+1,n,k,!status)- arr[i]) ;
            }
        }
        return dp[i][k][status] = ans;
    }
    int maxProfit(int k, vector<int>& prices) {
        pre();
        if(k>=prices.size()/2){
            int ans = 0;
            for(int i = 1; i < prices.size(); i++){
                if(prices[i] > prices[i-1])ans += prices[i] - prices[i-1];
            }
            return ans;
        }
        return solve(prices,0,prices.size(),k,0);
    }
};
main(){
    Solution ob;
    vector<int> v = {3,2,6,4,0,3};
    cout << (ob.maxProfit(2, v));
}

입력

{ 3,2,6,4,0,3 }