1. 주택 구매를 통한 안락함의 최댓값 계산

n명의 친구가 각각 일정량의 금화를 가지고 있고, m개의 매물이 있는 부동산 시장에서 주택을 구매하려고 합니다. 각 주택은 '안락함'과 '가격'이라는 두 가지 속성을 가집니다. 구매 조건은 다음과 같습니다.

• 한 사람은 최대 하나의 주택만 구매할 수 있습니다.
• 한 주택은 최대 한 명에게만 팔릴 수 있습니다.
• 구매자의 금화는 주택 가격보다 크거나 같아야 합니다.

목표는 모든 친구가 구매한 주택의 안락함 합계를 최대화하는 것입니다.

풀이 전략: 안락함이 높은 주택을 우선적으로 선택하되, 해당 주택을 살 수 있는 사람 중 가장 적은 금화를 가진 사람을 매칭하는 그리디(Greedy) 방식을 사용합니다. 효율적인 탐색을 위해 std::multiset 또는 std::map을 활용하여 이진 탐색을 수행합니다.

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

using namespace std;

struct Property {
    int comfort;
    int cost;
};

int main() {
    int friendCount, houseCount;
    cin >> friendCount >> houseCount;

    multiset<int> budgetPool;
    for (int i = 0; i < friendCount; ++i) {
        int gold;
        cin >> gold;
        budgetPool.insert(gold);
    }

    vector<Property> houses(houseCount);
    for (int i = 0; i < houseCount; ++i) {
        cin >> houses[i].comfort >> houses[i].cost;
    }

    // 안락함 내림차순, 가격 오름차순 정렬
    sort(houses.begin(), houses.end(), [](const Property& a, const Property& b) {
        if (a.comfort == b.comfort) return a.cost < b.cost;
        return a.comfort > b.comfort;
    });

    long long totalComfort = 0;
    for (const auto& h : houses) {
        // 현재 주택 가격 이상인 금화를 가진 사람 중 최솟값 탐색
        auto it = budgetPool.lower_bound(h.cost);
        if (it != budgetPool.end()) {
            totalComfort += h.comfort;
            budgetPool.erase(it);
        }
    }

    cout << totalComfort << endl;
    return 0;
}

2. 진법 변환 시 숫자 '1'의 최대 개수 찾기

10진수 n이 주어졌을 때, 2진법부터 36진법까지의 모든 표현 방식 중에서 숫자 '1'이 가장 많이 포함되는 경우의 '1'의 개수를 구하는 문제입니다.

풀이 전략: 각 진법(2~36)에 대해 직접 변환 과정을 거치며 나머지가 1인 경우를 카운트하는 브루트 포스(Brute Force) 방식을 적용합니다.

#include <iostream>
#include <algorithm>

using namespace std;

int countOnesInBase(int num, int base) {
    int count = 0;
    while (num > 0) {
        if (num % base == 1) {
            count++;
        }
        num /= base;
    }
    return count;
}

int main() {
    int targetNum;
    cin >> targetNum;

    int maxOnes = 0;
    for (int b = 2; b <= 36; ++b) {
        maxOnes = max(maxOnes, countOnesInBase(targetNum, b));
    }

    cout << maxOnes << endl;
    return 0;
}

3. 비내림차순 시퀀스의 XOR 합 조건 만족시키기

길이가 n인 시퀀스 a가 다음 조건을 만족하는 경우의 수를 구해야 합니다.

• 모든 원소는 0 이상 m 이하의 정수입니다.
• 시퀀스는 비내림차순(a[i] ≤ a[i+1])입니다.
• 모든 원소의 XOR 합은 m이어야 합니다.

풀이 전략: 동적 계획법(DP)을 사용합니다. dp[i][xorSum][lastValue]를 'i번째 원소까지 고려했을 때 XOR 합이 xorSum이고 마지막 원소의 값이 lastValue인 경우의 수'로 정의합니다. 시간 복잡도를 줄이기 위해 누적 합(Prefix Sum) 최적화를 통해 마지막 원소의 범위를 효율적으로 처리합니다.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;

    // XOR 합의 상한선 설정 (m의 비트 범위 고려)
    int limit = 1;
    while (limit <= m) limit <<= 1;
    if (limit < 1) limit = 1; 

    // dp[xor_val][last_val]
    vector<vector<long long>> dp(limit, vector<long long>(m + 1, 0));
    
    // 초기 상태: 0개의 숫자를 선택했을 때 XOR 합은 0
    for (int v = 0; v <= m; ++v) {
        dp[v][v] = 1;
    }

    // 두 번째 숫자부터 n번째 숫자까지 처리
    for (int i = 2; i <= n; ++i) {
        vector<vector<long long>> next_dp(limit, vector<vector<long long>>(m + 1, 0));
        
        for (int x = 0; x < limit; ++x) {
            long long prefixSum = 0;
            for (int v = 0; v <= m; ++v) {
                prefixSum = (prefixSum + dp[x ^ v][v]) % MOD;
                next_dp[x][v] = prefixSum;
            }
        }
        dp = move(next_dp);
    }

    long long result = 0;
    if (n == 1) {
        result = 1; // n이 1이면 a[0] = m인 경우 한 가지
    } else {
        for (int v = 0; v <= m; ++v) {
            result = (result + dp[m][v]) % MOD;
        }
    }

    cout << result << endl;
    return 0;
}