[백준] 2822번 점수 계산 (C++)

yeonjiyooo·2023년 3월 6일

PS

목록 보기

1/21

✍ 문제

상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다. 문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은 점수 5개의 합이다.

상근이는 잠시 여자친구와 전화 통화를 하느라 참가자의 점수를 계산하지 않고 있었다. 참가자의 8개 문제 점수가 주어졌을 때, 총 점수를 구하는 프로그램을 작성하시오.

✍ 입력

8개 줄에 걸쳐서 각 문제에 대한 참가자의 점수가 주어진다. 점수는 0보다 크거나 같고, 150보다 작거나 같다. 모든 문제에 대한 점수는 서로 다르다. 입력으로 주어지는 순서대로 1번 문제, 2번 문제, ... 8번 문제이다.

✍ 출력

첫째 줄에 참가자의 총점을 출력한다. 둘째 줄에는 어떤 문제가 최종 점수에 포함되는지를 공백으로 구분하여 출력한다. 출력은 문제 번호가 증가하는 순서이어야 한다.

✅ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

bool cmp (vector<int>& v1, vector<int>& v2) {
	return v1[1] < v2[1];
}

int main() {
	int score;
	int max_sum =0;
	vector<vector<int>> v;

	for (int i = 0; i < 8; i++) {
		cin >> score;
		v.push_back({score,i+1});
	}
	
	sort(v.begin(), v.end());
	
	for (int i = 3; i < 8; i++) {
		max_sum += v[i][0];
	}

	cout << max_sum << endl;

	v.erase(v.begin(), v.begin() + 3);
	sort(v.begin(), v.end(),cmp);
	
	for (int i = 0; i < 5; i++) {
		cout << v[i][1] << " ";
	}

	return 0;

}

✅ 코드풀이

2822번은 참가자의 총점, 그리고 총점에 포함되는 문제 번호들을 구해야 하는 문제였다.
총점은 입력값을 2차원 vector에 받아 오름차순으로 정렬한 후, v[0][3]부터 v[0][7]까지의 합으로 간단히 구할 수 있었다.

✔️정렬

각 문제의 점수가 담긴 vector를 정렬하기 위해서 algorithm 헤더에 포함되어 있는 sort 함수를 사용하였다.
이는 c++의 STL에서 제공하는 함수로 시간복잡도가 nlogn이다.
sort 함수는 intro sort라는 정렬방식으로 구현되었으며 이는 quick sort를 기반으로 heap sort와 insertion sort를 섞은 방식이다.