시험 공부 (Studying for Exams)

> 문제 출처

https://www.codeground.org/practice/

3 Practice Studying for Exams

 

> 문제 설명

 초등학생인 정우는 시험 기간을 맞아 공부를 시작해야 한다.
 정우가 다니는 학교에선 총 N개의 과목에 대해 시험을 보는데, 시간이 부족한 정우는 그 중 K개의 과목만을 골라서 공부할 수 있다.
 정우는 매우 특이한 학생이라서 어떤 과목을 공부한다면 그 과목에 대해선 무조건 같은 점수를 받게 된다고 한다.
 정우는 시험 점수 총합을 최대화하기 위해 K개의 과목을 골라야 한다.
 하지만, 모든 과목을 공부할 시간이 없는 정우는, 당신에게 "최대 합계 점수"를 받을 수 있는 K개의 과목을 골라달라고 한다.
 K개 과목을 골랐을 때 정우가 받을 수 있는 "최대 합계 점수"를 구하는 프로그램을 작성하라.

정상이라면 암산으로도 할 수 있는 문제이지만 미친 학교가 최대 20만개 과목의 시험을 본다고 한다.

> 접근 방법

 모든 점수를 입력받고 정렬을 실행한 후 가장 높은 점수부터 K개만큼을 더하면 정답이 되는 아주 간단한 문제이다.

 

 array를 이용해 풀었던 문제인데 input > sort > calculate과정 대신 list를 이용하여 input을 하면서 다 처리하면 더 빨리 풀리지 않을까 했지만...

TestCase가 커지게 될 경우에 iteration과 sorting이 너무 많아져 미친 실행시간을 보여주었다.

 

> CODE

 

+ cin/cout은 스트림 객체라 작동이 조금 복잡하게 된다는건 대충 알고있었는데 이정도의 차이를 보일지는 몰랐다.

왼쪽의 코드를 scanf/printf로 제출했을때의 속도. 상당히(2배나!) 빨라졌다

 

++ 프로그래밍 언어별 입출력 속도를 높이는 방법에 대해 소개한 글. 프로그래밍 문제/대회를 연습하는 분들께는 좋은 정보가 될 것 같다.

https://www.acmicpc.net/board/view/22716

 

---

https://github.com/dongha-yoon/ProgrammingStudy - studing_for_exams_old/new.cpp