[알고리즘] 참고

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;

///////////////////////////////////////////////////////
// 1. k-LCS (2차원 점화식 기반) - O(N^2)
// 파일 입력: input_kLCS.txt
// 형식: 첫 줄 k, 둘째 줄 문자열 X, 셋째 줄 문자열 Y
///////////////////////////////////////////////////////

int kLCS(const string& X, const string& Y, int k) {
    int n = X.size(), m = Y.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                int max_prev = 0;
                for (int p = max(1, i - k); p < i; ++p) {
                    for (int q = max(1, j - k); q < j; ++q) {
                        if (X[p - 1] == Y[q - 1]) {
                            max_prev = max(max_prev, dp[p][q]);
                        }
                    }
                }
                dp[i][j] = max(1, max_prev + 1);
            } else {
                dp[i][j] = 0;
            }
        }
    }

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

///////////////////////////////////////////////////////
// 2. 상자쌓기 - 최대 개수 (DP 기반) - O(N * Cmax)
// 파일 입력: input_boxes.txt
// 형식: 첫 줄 상자 개수 N, 이후 N줄에 weight와 capacity
///////////////////////////////////////////////////////

struct Box {
    int weight, capacity;
};

int maxStackableBoxes(vector<Box>& boxes) {
    int N = boxes.size();
    sort(boxes.begin(), boxes.end(), [](const Box& a, const Box& b) {
        return a.capacity + a.weight > b.capacity + b.weight; // LCWF
    });

    int Cmax = 0;
    for (auto& b : boxes) Cmax = max(Cmax, b.capacity);

    vector<vector<int>> dp(N + 1, vector<int>(Cmax + 1, 0));

    for (int i = N - 1; i >= 0; --i) {
        for (int w = 0; w <= Cmax; ++w) {
            dp[i][w] = dp[i + 1][w]; // skip
            if (boxes[i].weight <= w) {
                int nextW = min(boxes[i].capacity, w - boxes[i].weight);
                dp[i][w] = max(dp[i][w], 1 + dp[i + 1][nextW]);
            }
        }
    }
    return dp[0][Cmax];
}

///////////////////////////////////////////////////////
// 사용 예시 (ifstream 기반 입력 처리)
///////////////////////////////////////////////////////
int main() {
    // k-LCS 입력
    ifstream in1("input_kLCS.txt");
    int k;
    string X, Y;
    in1 >> k >> X >> Y;
    cout << "k-LCS (2차원 점화식) 결과: " << kLCS(X, Y, k) << endl;
    in1.close();

    // 상자쌓기 입력
    ifstream in2("input_boxes.txt");
    int N;
    in2 >> N;
    vector<Box> boxes(N);
    for (int i = 0; i < N; ++i) {
        in2 >> boxes[i].weight >> boxes[i].capacity;
    }
    cout << "상자쌓기 최대 개수: " << maxStackableBoxes(boxes) << endl;
    in2.close();

    return 0;
}