백준 17224번 [APC는 왜 서브태스크 대회가 되었을까?](C++) -yes6686- 티스토리

 

백준 문제 풀이: 17224 [APC는 왜 서브태스크 대회가 되었을까?]

---

문제 링크: https://www.acmicpc.net/problem/17224

문제 설명:

서브태스크 형식으로 진행되는 대회에서 참가자가 풀 수 있는 문제의 최대 점수를 계산하세요. 문제마다 난이도가 주어지며, 참가자의 실력을 고려하여 문제를 푼 점수를 누적합니다.

입력 조건:

• 첫 번째 줄에 문제 수 n, 참가자의 실력 l, 풀 수 있는 최대 문제 수 k가 주어집니다. (1 ≤ n, k ≤ 100, 1 ≤ l ≤ 10)
• 다음 n개의 줄에는 각 문제의 쉬운 버전의 난이도와 어려운 버전의 난이도가 주어집니다. (1 ≤ 쉬운 버전 난이도 ≤ 어려운 버전 난이도 ≤ 10)

출력 조건:

• 참가자가 얻을 수 있는 최대 점수를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> arr[101];

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

    int n, l, k;
    cin >> n >> l >> k;

    int sum = 0;
    int cnt = 0;

    // 입력받은 난이도를 pair로 저장 (어려운 난이도, 쉬운 난이도)
    for (int i = 0; i < n; i++) {
        cin >> arr[i].second >> arr[i].first;
    }

    // 어려운 난이도를 기준으로 오름차순 정렬
    sort(arr, arr + n);

    for (int i = 0; i < n; i++) {
        if (cnt >= k) break; // 최대 문제 수를 초과하면 종료

        if (arr[i].first <= l) { // 어려운 난이도를 풀 수 있는 경우
            sum += 140;
            cnt++;
        } else if (arr[i].second <= l) { // 쉬운 난이도만 풀 수 있는 경우
            sum += 100;
            cnt++;
        }
    }

    cout << sum << '\n'; // 누적 점수 출력
    return 0;
}
    

---

코드 설명

위 코드는 참가자가 서브태스크 형식의 대회에서 얻을 수 있는 최대 점수를 계산합니다.

• 입력 처리:
  • 문제의 난이도를 `pair`로 저장하며, 첫 번째 값은 어려운 버전의 난이도, 두 번째 값은 쉬운 버전의 난이도입니다.
• 정렬:
  • 어려운 난이도를 기준으로 오름차순 정렬하여 문제를 효율적으로 선택할 수 있도록 합니다.
• 점수 계산:
  • 참가자의 실력으로 풀 수 있는 문제를 확인하며 최대 점수를 계산합니다.
  • 어려운 버전을 풀 수 있으면 140점을 추가, 그렇지 않으면 쉬운 버전을 풀어 100점을 추가합니다.
  • 최대 `k` 문제까지만 점수를 누적합니다.

시간 복잡도 분석:

• 정렬: O(n log n).
• 점수 계산: O(n).
• 전체 시간 복잡도: O(n log n), n은 문제의 개수.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
5 4 3
3 5
4 6
2 8
1 4
3 6

출력:
340

참가자는 최대 3문제를 풀어 총 340점을 얻을 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!