백준 APC는 왜 서브태스크 대회가 되었을까? 코틀린 그리디알고리즘

https://www.acmicpc.net/problem/17224

17224번: 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

서브태스크 1 (100점)

• K = N

서브태스크 2 (40점)

• 0 ≤ K ≤ N

예제 입력 1 복사

4 8 4

1 8

4 5

6 20

9 12

예제 출력 1 복사

380

1번, 2번 문제의 어려운 버전을 해결해 2×140 = 280점을, 3번 문제의 쉬운 버전을 해결해 100점을 얻어 총 380점을 얻는다.

현정이가 4문제를 풀 수 있을 정도로 대회 시간은 충분하지만, 4번 문제는 현정이에겐 너무 어려워서 풀 수 없다.

예제 입력 2 복사

8 7 5

1 3

2 5

3 5

4 8

5 8

6 9

6 7

7 10

예제 출력 2 복사

660

예제 입력 3 복사

8 9 5

1 8

3 10

4 5

5 20

7 12

8 15

9 50

14 14

예제 출력 3 복사

580

힌트

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

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

 

 

---

이 문제는 좀 특이하게 예제 1번 만 되는 답 (100점짜리 문제) 와 2번답까지 풀 수있는 답(140점짜리 문제) 2가지 유형이 있습니다

 

예제 1번만 되는 코드같은 경우 예제 2번,3번 은 풀리지 않습니다

 

이 문제가 원하는 것은 현정이가 APC 에 참가했을때 최대 점수를 출력하는 문제입니다!

 

서브태스크 1번만 해당하는 코드는 그냥 N개 중에서 자신의 역량이 sub2 보다 큰 경우 +140 아닌경우는 sub1에 따라서 100점 혹은 못푸는 것으로 나뉘어 질 수 있습니다

 

그러나 서브태스크 2번 을 풀기 위해서는 

sub1 과 sub2의 난이도를 저장하는 리스트가 각각 따로 있어야 하고 

내림차순으로 정렬 후 

최대한 140점을 얻은 다음 

남은 문제 수를 100점으로 얻어야 합니다! 

아 그리고 해시맵을 통해서 푼 문제의 번호를 해시맵에 넣은 다음 

똑같은 문제를 연속해서 못 풀게 했습니다!

 

 

fun main(){
    var answer = 0
   var str = readLine()
    var array = str!!.split(" ")
    var sub1 = ArrayList<Int>()
    var sub2 = ArrayList<Int>()
    var map = HashMap<Int,Boolean>()
    for(i in 0 until array[0].toInt()){
        var question = readLine()
        var questionArray = question!!.split(" ")
        sub1.add(questionArray[0].toInt())
        sub2.add(questionArray[1].toInt())
    }
    sub1.sortDescending()
    sub2.sortDescending()
    for(i in sub2.indices ){
        if(map.size==array[2].toInt()){
            break
        }
        if(map.size<=array[2].toInt() && sub2[i].toInt()<=array[1].toInt()){
            answer +=140
            map.put(i,true)
        }
    }
    for(i in 0 until array[0].toInt()){
        if(map.size==array[2].toInt()){
            break
        }
        if(sub1[i].toInt()<=array[1].toInt() && map.containsKey(i).not()){
            answer +=100
            map.put(i,true)
        }

    }
println(answer)
}