[C++] 백준 17224 APC는 왜 서브태스크 대회가 되었을까?

www.acmicpc.net/problem/17224

17224번: APC는 왜 서브태스크 대회가 되었을까?

 

1. 서론

 

약간 생각해줘야 하는 사항이 있는 문제다.

 

2. 문제 풀이

 

프로그래밍 대회가 개최된다. 한 문제가 쉬운 버전, 어려운 버전으로 나뉘어서 주어진다. 문제는 각각 난이도가 숫자로 주어진다.

쉬운 버전을 풀면 100점, 어려운 버전을 풀면 140점을 점수로 준다.

입력으로 문제의 총 개수와 한 학생이 풀 수 있는 문제의 수준(숫자로 주어진 난이도) 그리고 최대로 풀 수 있는 개수가 주어진다. 

이것들을 활용해 한 학생이 대회에서 얻을 수 있는 최대 점수를 구하는 것이 문제이다.

 

최대 점수를 받아야 하는 문제이기 때문에 가능하다면 어려운 버전을 풀어서 맞는 것이 좋다. 그래서 나는 쉬운 난이도와 어려운 난이도 중 어려운 문제의 난이도를 먼저 봤다. 어려운 문제의 난이도가 이 학생이 풀 수 있는 경우를 체크하는 것이다. 그리고 가능한 경우를 체크한 후, 어려운 버전은 난이도가 높아 풀 수 없고 쉬운 버전은 풀 수 있는 문제를 체크한다. 이때, 한 학생이 풀 수 있는 문제의 개수를 체크하는 것이다. 140점짜리를 먼저 계산하고 100점짜리를 나중에 계산하니까 최대 점수를 구할 수 있다.

 

3. 코드 설명

 

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int n, l, k, i, a, b, s = 0;
    vector<pair<int, int>> v; 

    cin >> n >> l >> k;

    for (i = 0; i < n; i++)
    {
        cin >> a >> b;
        v.push_back(make_pair(a, b));
    }

    for (i = 0; i < n; i++)
    {
        if (k == 0) break;

        if (l >= v[i].second)
        {
            s += 140;
            k--;
        }  
    }

    for (i = 0; i < n; i++)
    {
        if (k == 0) break;

        if (l >= v[i].first && l < v[i].second)
        {
            s += 100;
            k--;
        }   
    }

    cout << s << endl;
}

 

vector에서 pair로 한 문제를 묶어준다. first 부분에는 문제의 쉬운 난이도를 second에는 문제의 어려운 난이도를 넣어준다. 

그리고 second의 값보다 작거나 같은 것은 풀 수 있는 문제이므로 count하고 k로 문제의 개수를 count 해준다. second 값을 다 계산한 후에는 first의 값에 해당하는 문제와 점수를 count 해준다. 그렇게 하면 최대 점수를 구할 수 있다.