1. 참가자 순위 결정 및 상위 K명 선정

이 문제는 주어진 기준에 따라 참가자들의 점수를 계산하고, 이를 기반으로 상위 K명의 참가자를 선정하는 문제입니다. 선정된 참가자는 원래의 ID 순서로 정렬하여 출력해야 합니다.

각 참가자는 두 개의 값(x, y)을 가지고 있으며, 최종 점수는 x + 2*y로 계산됩니다. 점수가 같을 경우, 원래 ID가 작은 참가자가 우선순위를 가집니다. 최종적으로 상위 K명의 ID를 오름차순으로 정렬하여 출력합니다.

문제 해결 전략

1. 각 참가자의 ID와 계산된 점수를 저장하는 구조체를 정의합니다.
2. 정의된 기준(점수 내림차순, ID 오름차순)에 따라 참가자 목록을 정렬합니다.
3. 정렬된 목록에서 상위 K명의 참가자 ID를 추출합니다.
4. 추출된 ID들을 다시 오름차순으로 정렬하여 출력합니다.

C++ 코드 예시

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort

// 참가자 정보를 저장할 구조체
struct Contestant {
    int participant_id; // 원래 참가자 ID
    long long total_score; // 계산된 최종 점수
};

// 정렬을 위한 비교 함수
// 1. total_score가 높은 순서대로 정렬
// 2. total_score가 같으면 participant_id가 낮은(작은) 순서대로 정렬
bool compareContestants(const Contestant& a, const Contestant& b) {
    if (a.total_score != b.total_score) {
        return a.total_score > b.total_score;
    }
    return a.participant_id < b.participant_id;
}

int main() {
    // 입출력 속도 향상
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_contestants; // 총 참가자 수
    int select_k; // 선정할 상위 K명
    std::cin >> num_contestants >> select_k;

    std::vector<Contestant> contestants(num_contestants);
    for (int i = 0; i < num_contestants; ++i) {
        long long val_x, val_y;
        std::cin >> val_x >> val_y;
        contestants[i].participant_id = i + 1; // 1부터 시작하는 ID 부여
        contestants[i].total_score = val_x + 2 * val_y; // 점수 계산
    }

    // 정의된 비교 함수에 따라 참가자 정렬
    std::sort(contestants.begin(), contestants.end(), compareContestants);

    // 상위 K명의 ID를 저장할 벡터
    std::vector<int> top_k_ids;
    for (int i = 0; i < select_k; ++i) {
        top_k_ids.push_back(contestants[i].participant_id);
    }

    // 상위 K명의 ID를 오름차순으로 다시 정렬
    std::sort(top_k_ids.begin(), top_k_ids.end());

    // 결과 출력
    for (int i = 0; i < top_k_ids.size(); ++i) {
        std::cout << top_k_ids[i] << (i == top_k_ids.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

2. 최대 효율 프로젝트 선정

이 문제는 N개의 프로젝트 중 K개를 선택하여 총 가치를 최대화하는 문제입니다. 각 프로젝트는 두 가지 속성(생산성 a, 마감 기한 b)을 가집니다. 프로젝트 집합의 총 가치는 (선택된 K개 프로젝트의 생산성 합) * (선택된 K개 프로젝트 중 가장 짧은 마감 기한)으로 정의됩니다.

핵심은 마감 기한이 짧은 프로젝트가 전체 가치에 큰 영향을 미치므로, 마감 기한을 기준으로 프로젝트를 정렬하고, 우선순위 큐를 활용하여 생산성 합을 효율적으로 관리하는 것입니다.

문제 해결 전략

1. 모든 프로젝트를 마감 기한(b)이 긴 순서대로 정렬합니다. 이렇게 하면 현재 보고 있는 프로젝트 P_i의 마감 기한 P_i.b가 현재까지 고려된 모든 프로젝트 중 가장 짧은 마감 기한이 됩니다 (P_i.b를 포함하여 K개의 프로젝트를 선택할 경우).
2. 생산성 a를 저장할 최소 힙(min-priority queue)을 사용합니다. 이 힙은 항상 선택된 K개의 프로젝트 중 가장 작은 생산성을 가진 프로젝트를 쉽게 찾고 제거할 수 있도록 돕습니다.
3. 정렬된 프로젝트를 순회하면서:
   • 현재 프로젝트의 생산성을 최소 힙에 추가하고, 현재 선택된 프로젝트들의 생산성 합계에 더합니다.
   • 만약 최소 힙의 크기가 K보다 커지면, 가장 작은 생산성(힙의 최상단)을 가진 프로젝트를 제거하고 합계에서 뺍니다.
   • 힙의 크기가 K가 되면, 현재 생산성 합계와 현재 프로젝트의 마감 기한(P_i.b)을 곱하여 총 가치를 계산하고, 최대 가치를 갱신합니다.

C++ 코드 예시

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort
#include <queue>     // for std::priority_queue

// 프로젝트 정보를 저장할 구조체
struct Project {
    long long productivity; // 생산성 (original 'a')
    long long deadline;     // 마감 기한 (original 'b')
};

// 프로젝트를 마감 기한 내림차순으로 정렬하기 위한 비교 함수
bool compareProjectsByDeadline(const Project& p1, const Project& p2) {
    return p1.deadline > p2.deadline;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_projects; // 총 프로젝트 수 (N)
    int num_select_k; // 선택할 프로젝트 수 (K)
    std::cin >> num_projects >> num_select_k;

    std::vector<Project> projects(num_projects);
    for (int i = 0; i < num_projects; ++i) {
        std::cin >> projects[i].productivity;
    }
    for (int i = 0; i < num_projects; ++i) {
        std::cin >> projects[i].deadline;
    }

    // 프로젝트를 마감 기한 내림차순으로 정렬
    std::sort(projects.begin(), projects.end(), compareProjectsByDeadline);

    long long max_total_value = 0;
    long long current_efficiency_sum = 0;
    // 최소 힙: K개 프로젝트 중 가장 작은 생산성을 추적
    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> min_pq_efficiencies;

    for (int i = 0; i < num_projects; ++i) {
        // 현재 프로젝트의 생산성을 합계에 추가하고 힙에 삽입
        current_efficiency_sum += projects[i].productivity;
        min_pq_efficiencies.push(projects[i].productivity);

        // 힙의 크기가 K를 초과하면 가장 작은 생산성을 가진 프로젝트 제거
        if (min_pq_efficiencies.size() > num_select_k) {
            current_efficiency_sum -= min_pq_efficiencies.top();
            min_pq_efficiencies.pop();
        }

        // 힙에 정확히 K개의 프로젝트가 있을 때 총 가치 계산 및 최대값 갱신
        if (min_pq_efficiencies.size() == num_select_k) {
            // 현재 projects[i].deadline은 현재 K개 프로젝트 집합의 최소 마감 기한이 된다.
            max_total_value = std::max(max_total_value, current_efficiency_sum * projects[i].deadline);
        }
    }

    std::cout << max_total_value << std::endl;

    return 0;
}

3. 제한된 조건 하의 수열 생성 경우의 수 계산

이 문제는 길이 N의 수열 x_1, x_2, ..., x_N을 생성하는 경우의 수를 계산합니다. 각 원소 x_i는 1부터 M까지의 정수 값을 가질 수 있습니다. 수열의 인접한 원소 x_i와 x_{i-1} 사이에는 주어진 문자열 S에 따라 특정 관계('=', '<', '>')가 적용됩니다.

• S[i-2] == '=': x_i = x_{i-1}
• S[i-2] == '<': x_i > x_{i-1}
• S[i-2] == '>': x_i < x_{i-1}

모든 경우의 수는 특정 모듈로 값(10^9 + 7)으로 나눈 나머지를 출력해야 합니다.

문제 해결 전략 (동적 계획법)

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다.

1. DP 상태 정의: dp_count[i][j]를 길이가 i이고 마지막 원소 x_i의 값이 j인 유효한 수열의 개수라고 정의합니다.
2. 누적 합 배열: cumulative_ways_up_to_value[j]를 길이가 i-1인 수열에서 마지막 원소의 값이 j 이하인 모든 경우의 수의 합으로 정의합니다. 이 배열은 각 i 단계에서 dp_count[i-1][k]의 합을 효율적으로 계산하는 데 사용됩니다.
3. 점화식: dp_count[i][j]를 계산하기 위해 S[i-2]의 관계에 따라 다음과 같이 이전 상태의 값들을 활용합니다.
   • S[i-2] == '=': dp_count[i][j] = dp_count[i-1][j]
   • S[i-2] == '<': dp_count[i][j] = cumulative_ways_up_to_value[j-1] (즉, x_{i-1} < j인 경우의 수 합)
   • S[i-2] == '>': dp_count[i][j] = (cumulative_ways_up_to_value[M] - cumulative_ways_up_to_value[j] + MOD) % MOD (즉, x_{i-1} > j인 경우의 수 합)
4. 기저 사례: 길이가 1인 수열의 경우, x_1은 1부터 M까지 어떤 값도 가질 수 있으므로 dp_count[1][j] = 1입니다. cumulative_ways_up_to_value도 이에 따라 초기화됩니다.
5. 최종 결과: 모든 dp_count[N][j] (j는 1부터 M까지)의 합이 최종 답이 됩니다. 모든 계산은 모듈로 연산을 적용하여 오버플로우를 방지합니다.

C++ 코드 예시

#include <iostream>
#include <vector>
#include <string>
#include <numeric> // Not strictly used for iota, but can be helpful
#include <algorithm> // For std::fill (though not directly in the final version)

const int MAX_LEN = 2005; // 최대 수열 길이
const int MAX_VAL = 2005; // 최대 원소 값
const int MOD = 1e9 + 7;  // 모듈로 값

long long ways_at_length_and_value[MAX_LEN][MAX_VAL]; // dp_count[i][j]
long long cumulative_ways_up_to_value[MAX_VAL];      // cumulative_ways_up_to_value[j] for length (i-1)

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int sequence_len_n;    // 수열의 길이 (N)
    int max_val_m;         // 원소의 최대값 (M)
    std::string relation_symbols; // 인접 원소 관계 문자열 (S)

    std::cin >> sequence_len_n >> max_val_m >> relation_symbols;

    // 기저 사례: 길이가 1인 수열
    // x_1은 1부터 max_val_m까지 어떤 값도 가능하므로 각 경우의 수는 1
    for (int val = 1; val <= max_val_m; ++val) {
        ways_at_length_and_value[1][val] = 1;
        // cumulative_ways_up_to_value 배열 초기화 (길이 1에 대한 누적 합)
        cumulative_ways_up_to_value[val] = (cumulative_ways_up_to_value[val - 1] + ways_at_length_and_value[1][val]) % MOD;
    }

    // 길이가 2부터 sequence_len_n까지 수열을 구성
    for (int current_len = 2; current_len <= sequence_len_n; ++current_len) {
        // current_len-1과 current_len 사이의 관계 심볼
        // relation_symbols는 0-indexed이고, S[i-2]는 x_i와 x_{i-1}의 관계를 나타내므로
        // current_len이 2일 때 relation_symbols[0]을 사용
        char current_relation = relation_symbols[current_len - 2]; 

        // 현재 길이(current_len)에 대한 누적 합을 계산하기 위한 임시 배열
        // 이 배열은 ways_at_length_and_value[current_len][j]가 모두 계산된 후
        // 다음 반복(current_len + 1)을 위해 cumulative_ways_up_to_value에 반영됩니다.
        long long temp_cumulative_sums_for_current_len[MAX_VAL] = {0};

        for (int current_val = 1; current_val <= max_val_m; ++current_val) {
            if (current_relation == '=') {
                // x_current_len = x_{current_len-1}
                ways_at_length_and_value[current_len][current_val] = ways_at_length_and_value[current_len - 1][current_val];
            } else if (current_relation == '<') {
                // x_current_len > x_{current_len-1}
                // 이전 길이에서 current_val보다 작은 값으로 끝나는 모든 경우의 수 합
                ways_at_length_and_value[current_len][current_val] = cumulative_ways_up_to_value[current_val - 1];
            } else if (current_relation == '>') {
                // x_current_len < x_{current_len-1}
                // 이전 길이에서 current_val보다 큰 값으로 끝나는 모든 경우의 수 합
                // (이전 길이 총 경우의 수 - 이전 길이에서 current_val 이하로 끝나는 경우의 수)
                long long total_ways_prev_len = cumulative_ways_up_to_value[max_val_m];
                long long ways_up_to_current_prev_len = cumulative_ways_up_to_value[current_val];
                ways_at_length_and_value[current_len][current_val] = (total_ways_prev_len - ways_up_to_current_prev_len + MOD) % MOD;
            }
            // 현재 길이(current_len)의 dp_count[current_len][current_val]까지의 누적 합 계산
            temp_cumulative_sums_for_current_len[current_val] = 
                (temp_cumulative_sums_for_current_len[current_val - 1] + ways_at_length_and_value[current_len][current_val]) % MOD;
        }
        
        // 현재 길이(current_len)의 누적 합을 다음 반복(current_len + 1)을 위해 반영
        for(int val = 1; val <= max_val_m; ++val) {
            cumulative_ways_up_to_value[val] = temp_cumulative_sums_for_current_len[val];
        }
    }

    long long final_total_ways = 0;
    // 최종 결과: 길이가 sequence_len_n인 모든 수열의 경우의 수 합
    for (int val = 1; val <= max_val_m; ++val) {
        final_total_ways = (final_total_ways + ways_at_length_and_value[sequence_len_n][val]) % MOD;
    }

    std::cout << final_total_ways << std::endl;

    return 0;
}