동적 계획법(Dynamic Programming)에서 상태 머신(State Machine) 개념을 도입하면 복잡한 의사결정 과정을 간결한 상태 전이 방정식으로 변환할 수 있습니다. 각 단계에서의 선택지를 상태로 정의하고, 이전 상태로부터 현재 상태로 도달하는 최적 경로를 계산하는 세 가지 사례를 살펴봅니다.

1. 인접한 항목을 선택할 수 없는 경우 (도둑 문제)

연속된 상점을 털 수 없는 제약 조건 하에서 최대 수익을 구하는 문제입니다. 상태는 '현재 상점을 털지 않음(상태 0)'과 '현재 상점을 털음(상태 1)'으로 구분합니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n; cin >> n;
        vector<int> values(n + 1);
        for (int i = 1; i <= n; i++) cin >> values[i];

        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + values[i];
        }
        cout << max(dp[n][0], dp[n][1]) << endl;
    }
    return 0;
}

2. 거래 횟수가 제한된 주식 매매

최대 K번의 거래가 가능할 때, '주식을 보유 중(상태 1)'과 '보유하지 않음(상태 0)'을 기반으로 3차원 DP 배열을 구성합니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int INF = 1e9;

int main() {
    int n, k; cin >> n >> k;
    vector<int> prices(n + 1);
    for (int i = 1; i < i++) cin >> prices[i];

    // dp[거래횟수][보유상태]
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(2, -INF)));
    
    for (int i = 0; i <= n; i++) dp[i][0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
        }
    }
    int result = 0;
    for (int j = 0; j <= k; j++) result = max(result, dp[n][j][0]);
    cout << result;
    return 0;
}

3. 냉각 기간이 있는 주식 매매

매도 후 하루의 냉각기가 필요한 상황입니다. 이를 위해 '보유 중', '오늘 매도함', '냉각 중(또는 보유하지 않음)'의 세 가지 상태를 정의하여 전이합니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int NEG_INF = -1e9;

int main() {
    int n; cin >> n;
    vector<int> prices(n + 1);
    for (int i = 1; i <= n; i++) cin >> prices[i];

    // 상태: 0-보유중, 1-방금매도, 2-냉각/휴식
    vector<vector<int>> dp(n + 1, vector<int>(3, 0));
    dp[0][0] = dp[0][1] = NEG_INF;
    dp[0][2] = 0;

    for (int i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
        dp[i][1] = dp[i - 1][0] + prices[i];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]);
    }
    cout << max(dp[n][1], dp[n][2]);
    return 0;
}