1. 정수 합 구성 문제 (2022)

서로 다른 10 개의 양정수를 선택하여 그 합이 2022 가 되는 경우의 수를 구하는 문제입니다. 이는 제한 조건이 두 개 존재하는 배낭 문제 변형으로 볼 수 있습니다.

접근 방식

1 부터 2022 까지의 숫자를物品으로 간주합니다. 각 숫자는 그 자체의 값을 비용 (weight) 으로 가지며, 선택된 숫자의 개수도 제한 조건이 됩니다. 따라서 상태 공간은 [선택된 개수][현재 합] 으로 정의할 수 있습니다. 기본적인 0/1 배낭 문제 로직에 개수를 세는 차원을 추가하여 구현합니다.

구현 코드

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    // dp[count][sum]: count 개의 숫자를 선택하여 합이 sum 이 되는 경우의 수
    long long dp[11][2023] = {0};
    dp[0][0] = 1;

    // 1 부터 2022 까지의 숫자를 하나씩 고려
    for (int num = 1; num <= 2022; ++num) {
        // 개수는 역순으로 순회하여 중복 선택 방지 (0/1 배낭 최적화)
        for (int count = 10; count >= 1; --count) {
            // 합은 현재 숫자 이상부터 순회
            for (int currentSum = num; currentSum <= 2022; ++currentSum) {
                dp[count][currentSum] += dp[count - 1][currentSum - num];
            }
        }
    }

    cout << dp[10][2022] << endl;
}

2. 벽돌 쌓기 최적화 문제

주어진 n 개의 벽돌을 쌓을 때, 각 벽돌 위에 쌓인 벽돌들의 총 무게가 해당 벽돌의 내구도 (value) 를 초과하지 않도록 해야 합니다. 이때 얻을 수 있는 최대 내구도 합을 구하는 문제입니다.

접근 방식

벽돌을 쌓는 순서가 중요합니다. 위에 오는 벽돌일수록 무게가 가볍고 내구도가 큰 것이 유리합니다. 그리디 접근을 위해 각 벽돌의 무게 + 내구도 합을 기준으로 오름차순 정렬합니다. 정렬된 순서대로 배낭 문제 기법을 적용하여 최대 값을 계산합니다.

구현 코드

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

using namespace std;

struct Brick {
    int weight;
    int durability;
};

void solve() {
    int n;
    cin >> n;
    vector<Brick> bricks(n);
    int totalWeight = 0;

    for (int i = 0; i < n; ++i) {
        cin >> bricks[i].weight >> bricks[i].durability;
        totalWeight += bricks[i].weight;
    }

    // 무게 + 내구도 합을 기준으로 정렬
    sort(bricks.begin(), bricks.end(), [](const Brick& a, const Brick& b) {
        return (a.weight + a.durability) < (b.weight + b.durability);
    });

    vector<int> dp(totalWeight + 1, 0);
    int maxValue = 0;

    for (const auto& brick : bricks) {
        for (int w = totalWeight; w >= brick.weight; --w) {
            // 현재 무게에서 해당 벽돌 무게를 뺀 나머지가 벽돌 내구도 이하여야 함
            if (w - brick.weight <= brick.durability) {
                dp[w] = max(dp[w], dp[w - brick.weight] + brick.durability);
            }
            maxValue = max(maxValue, dp[w]);
        }
    }

    cout << maxValue << endl;
}

3. 비용报销 날짜 제한 문제

여러 장의发票 (영수증) 가 있으며, 각각 날짜와 금액을 가지고 있습니다. 선택한发票들 간의 날짜 간격이 k 이상이어야 하며, 총 금액이 m 을 초과하지 않을 때 최대 금액을 구하는 문제입니다.

접근 방식

먼저 날짜를 연중 일 수 (1~365) 로 변환합니다. 각 날짜별로 받을 수 있는 최대 금액을 미리 계산해 둡니다. 이후 날짜를 순회하며, k 일 이전의 상태 값을 참조하여 현재 날짜의发票를 선택할지 말지 결정하는 동적 프로그래밍을 수행합니다.

구현 코드

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

using namespace std;

// 월과 일을 연중 일 수로 변환
int convertDate(int month, int day) {
    const int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int totalDays = day;
    for (int i = 1; i < month; ++i) {
        totalDays += daysInMonth[i];
    }
    return totalDays;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> maxExpense(366, 0);

    for (int i = 0; i < n; ++i) {
        int mm, dd, val;
        cin >> mm >> dd >> val;
        int dayIndex = convertDate(mm, dd);
        // 같은 날짜에 여러 장이 있다면 최대 값만 저장
        maxExpense[dayIndex] = max(maxExpense[dayIndex], val);
    }

    // DP 진행: dp[i] 는 i 일까지 고려했을 때의 최대 금액
    for (int i = 1; i <= 365; ++i) {
        int prevDay = max(0, i - k);
        // 현재 날짜의 금액을 더할 수 있는지 확인 (총합 제한 m 은 최종 결과에서 필터링하거나 상태에 포함 가능)
        // 여기서는 단순 최대합 구조로 작성하며 m 제한은 필요시 추가 조건으로 활용
        if (maxExpense[i] + maxExpense[prevDay] <= m) {
             maxExpense[i] = max(maxExpense[i - 1], maxExpense[i] + maxExpense[prevDay]);
        } else {
             maxExpense[i] = maxExpense[i - 1];
        }
    }

    cout << maxExpense[365] << endl;
}