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

1. 문제이해

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

2822번: 점수 계산

 

8개의 문제에 대한 점수가 주어진다.

참가자의 총 점수는 이 중 가장 높은 점수 5개의 합 일때,

첫째줄에 참가자의 총점, 둘째줄에 참가자가 푼 문제번호를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

비교적 간단한 문제이다.

입력받은 문제의 점수와 번호를 저장해, 점수가 높은 순서대로 정렬,

이중 상위 5개의 문제의 점수의 합과 번호를 차례대로 출력하기만 하면 된다.

 

그렇다면, 문제의 점수와 번호를 함께 저장하는 방법은 무엇이 있을까?

바로, class와 map 이 있다. 필자는 class를 사용했다.

그렇다면, 점수와 번호가 섞이지 않도록 정렬하는 방법은 무엇일까?

바로, 안정정렬이다. (stable_sort)

 

이전에도 비슷한 문제를 통해 안정정렬에 대해 알아본 적이 있는데,

다시 짚고 넘어가면, 안정정렬은 동일한 값에 대해 기존의 순서가 유지되는 정렬,

불안정정렬은 기존의 순서가 뒤바뀔 수 있는 정렬이다.

즉, 안정정렬은 원래 존재하던 순서를 중시하는 반면, 불안정정렬은 그렇지 않다는 것이다.

안정정렬에 대한 더 자세한 설명과 추가적인 문제는 아래 링크를 참고하자.

 

https://beginnerdeveloper-lit.tistory.com/11

[C++] 백준 10814번 나이순 정렬

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

class problem {
public :
	int score;      // 문제 점수
	int num;        // 문제 번호
};

// 문제의 점수를 기준으로 "내림차순" 정렬 
bool cmp(problem a, problem b) {
	return a.score > b.score;
}

int main() {
	problem* p = new problem[8];
	int sum = 0;
	int arr[8];    // 문제번호를 복사해, 따로 정렬해주기 위한 배열

	for (int i = 0; i < 8; i++) {
		cin >> p[i].score;
		p[i].num = i + 1;
	}

	// 안정정렬 (기존의 문제의 번호와 점수에 대한 순서가 바뀌지 X)
	stable_sort(p, p + 8, cmp);

	for (int i = 0; i < 5; i++) {
		sum += p[i].score;
		arr[i] = p[i].num;
	}

	// 문제의 번호만 순서대로 정렬
	sort(arr, arr + 5);

	cout << sum << "\n";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	
	return 0;
}

위와 같이, class problem을 선언하고,

변수로는 점수에 해당하는 score, 번호에 해당하는 num을 선언해주었다.

아래 cmp 함수는 class 변수인 score를 기준으로 내림차순 정렬해주기 위한 함수이다.

 

메인함수에서는 변수들을 선언하고,

8개의 문제의 점수들을 차례로 입력받아, p[i].score에 각각 저장한다.

이때 문제번호는, 첫 문제를 1로 기준으로 하기 때문에, i + 1 하여 저장한다.

 

문제의 점수들이 모두 입력되면, 안정정렬을 한다. (순서가 섞이지 않기 위함.)

점수를 기준으로 내림차순 안정정렬된 값들 중, 상위 5개의 점수들만 sum 에 더해준뒤,

이때 더해진 문제들의 번호는 arr 배열에 복사한다.

(문제의 번호들만 따로 정렬을 해준 뒤 출력하기 위함.)

복사된 arr 안의 문제번호 값들은 오름차순 정렬해준 뒤,

구해둔 sum 값과 함께, for문을 이용해 문제 번호를 하나씩 출력해주었다.

 

 

---

오늘은 소스코드의 풀이부분을 비교적 자세히 적어보았다.

사실 안정정렬을 이용하면 쉽게 풀 수 있는 문제였다.

개인적인 사정으로 인해서 업로드 날짜가 점점 뒤죽박죽해지고 있는데..

다시 빨리 1일 1 포스팅을 할 수 있게 되었으면 좋겠다.😥 

포스팅을 읽다가 잘못된 점이나, 궁금한 점이 생기면 언제든지 댓글로 남겨주세요😊