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

2019년에도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다! 올해 새로 APC 총감독을 맡은 준표는 대회 출제 과정에서 큰 고민에 빠졌다. APC에 참가하는 사람들이 너무 다양해 대회 문제 난이도를 정하기가 너무 어렵기 때문이다.

APC에는 프로그래밍 대회에 익숙하지 않은 학생과 전공이 아닌 학생도 많이 참가하기 때문에 누구나 풀거나 도전할 수 있는 난이도 곡선을 갖춰야 한다. 또 '경인지역 6개대학 연합 프로그래밍 경시대회 shake!'에 참가할 학교 대표 10인을 선발하는 대표 선발전으로서의 변별력도 갖춰야 하며, 외부인이 따로 참가할 수 있는 Open Contest가 동시에 열리기 때문에 소위 '고인물'이 한 시간도 안 되어 대회를 정복하는 일도 막고 싶다. 여기에 APC 출제진인 준표, 만영, 현정, 준서는 문제를 준비하느라 무척 고생했기 때문에 참가자가 모든 문제를 한 번씩은 읽어 주기를 바라는 마음도 있다.

욕심 많은 준표는 고민 끝에 이 많은 요구를 모두 만족시킬 한 가지 해결책을 제안했다. 하나의 문제를 제한 조건을 통해 쉬운 버전과 어려운 버전으로 나누고, 쉬운 버전만 맞혀도 부분 점수를 주는 서브태스크 문제로 대회를 구성하는 것이다. 그리고 이렇게 만든 문제를 쉬운 버전의 난이도순으로 배치하려 한다.

이렇게 문제를 준비하면 프로그래밍 대회에 익숙하지 않은 사람은 앞에서부터 따라가며 도전할 수 있어 쉬운 문제를 찾는 데 시간을 쓰지 않아도 되고, 어려운 버전으로 학교 대표 선발을 위한 변별력을 유지할 수 있으며, 모든 문제가 읽히기를 바라는 출제진의 소망도 이룰 수 있다!

<그림1> 출제중 평가한 문제들의 난이도 예시 (예제2)

<!-- 아래 이야기는 팩션입니다. -->

현정이는 APC에 한 번이라도 나가 보고 싶다는 소망이 있다. 하지만 이 소망은 여태까지 단 한 번도, 앞으로도 이루어질 리 없기 때문에 현정이가 입버릇처럼 하게 된 말이 있다.

• 현정 : 아~~ 나도 APC 참가만 했으면 상금 받는 건데~~~~~
• 준표 : ... 그건 아닌 것 같은데?

현정이의 근거 없는 자신감이 눈꼴스러운 준표는 출제 중에 평가한 문제 난이도로 현정이의 예상 점수를 알려 주고, 현정이가 현실을 받아들일 수 있도록 도와주려 한다.

현정이는 L만큼의 역량을 가지고 있어 L보다 작거나 같은 난이도의 문제를 풀 수 있다. 또 코딩이 느리기 때문에 대회 시간이 부족해 K개보다 많은 문제는 해결할 수 없다. 어떤 문제의 쉬운 버전을 해결하면 100점을 얻고, 어려운 버전을 해결하면 여기에 40점을 더 받아 140점을 얻는다. 어려운 버전을 해결하면 쉬운 버전도 함께 풀리므로 한 문제를 해결한 것으로 계산한다.

현정이가 APC에 참가했다면 최대 몇 점을 얻을 수 있었는지 알려 주자.

첫 줄에 문제의 개수 N, 현정이의 역량 L, 현정이가 대회 중에 풀 수 있는 문제의 최대 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 1 ~ N번째 문제의 쉬운 버전의 난이도 sub1, 어려운 버전의 난이도 sub2가 순서대로 주어진다.

현정이가 APC에 참가했다면 얻었을 점수의 최댓값을 출력한다.

• 1 ≤ N ≤ 100
• 1 ≤ L ≤ 50
• 1 ≤ sub1 ≤ sub2 ≤ 50

예제2, 3은 서브태스크1에서는 나오지 않는다.

전통적으로 APC는 쉬운 버전의 문제를 먼저 푸는 것이 정신건강과 안정적인 득점을 위해 좋다.