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

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

2822번: 점수 계산

 

요구사항

8개의 점수를 받아,

①상위 5개 점수의 합을 출력하고

② 5개 점수의 인덱스를 출력한다.

 

코드

 

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

using namespace std;

int main(){
    vector<pair<int, int>> v; // 2개짜리, 튜플형태 벡터
    vector<int> idx;
    int sum = 0;

    // 입력
    for (int i = 1; i <= 8; i++){
        int num;
        cin >> num;
        v.push_back(make_pair(num, i));
    }
    // 내림차순 정렬
    sort(v.begin(), v.end(), greater<pair<int, int>>()); 
    for (int i = 0; i < 5; i++){
        sum += v[i].first;
        // 인덱스를 다른 벡터로 넣기
        idx.push_back(v[i].second);
    }
    // 인덱스 오름차순 정렬
    sort(idx.begin(), idx.end());
    
    // 출력
    cout << sum << endl;    
    for (auto &i : idx){
        cout << i << ' ';
    }

    return 0;
}

 

 

 

1. 초기화 및 입력

    vector<pair<int, int>> v; // 2개짜리, 튜플형태 벡터
    vector<int> idx;
    int sum = 0;

    // 입력
    for (int i = 1; i <= 8; i++){
        int num;
        cin >> num;
        v.push_back(make_pair(num, i));
    }

 

여기서 pair은 STL 라이브러리에서 vector의 원소를 튜플처럼 2개로 넣는 것이 가능하다.

 

입력시 make_pair()를 통해 값을 넣을 수 있다.

 

2. v 정렬 (오름차순)

	// 내림차순 정렬
    sort(v.begin(), v.end(), greater<pair<int, int>>());

 

sort함수의 greater는 오름차순 정렬을 해준다. (내림차순은 생략 or less로 표현)

 

(여기서 오름차순 정렬은 첫 원소 기준으로 두 번째 원소와 짝으로 정렬이 된다.)

ex {(2,100), (1,200), (4,400), (3,200)} → {(1,200), (2,100), (3,200), (4,400)}

 

가장 큰 5개의 점수를 더하기 위해 오름차순 정렬 후 상위 5개를 더하기 위함이다.

 

3. 점수 합과 인덱스 정리

    for (int i = 0; i < 5; i++){
        sum += v[i].first;
        // 인덱스를 다른 벡터로 넣기
        idx.push_back(v[i].second);
    }
    // 인덱스 오름차순 정렬
    sort(idx.begin(), idx.end());

 

우선, v의 첫번째 원소 상위 5개를 더해주고 그것에 대응하는 5개 인덱스를 idx에 저장한다.

 

여기서 idx를 오름차순으로 정렬하는 이유는

 

어차피 출력되는 인덱스가 순서대로 해당되는 원소의 인덱스를 출력하므로 오름차순 정렬처럼 되기 때문이다.