Baekjoon 문제 1026번 보물

문제 출처: https://www.acmicpc.net/problem/1026

1026번: 보물

Baekjoon 1026번 문제 보물

---

해당 문제를 빠르게 풀기 위해서는 A는 오름차순으로, B는 내림차순으로 정렬하여 서로 곱해주는 방법이 있다. 하지만 문제에는 B는 재배열하지 말라고 나와있다. 그럼 다시 생각해보자. 예제 1번을 볼때, A와 B를 정렬해서 보면 {A: 0, 1, 1, 1, 6} {B: 8, 7, 3, 2, 1}로 나타낼 수 있으며 각각 0-8, 1-7, 1-3, 1-2, 6-1로 매칭된다. 이 매칭쌍을 유지한 체 B를 원래의 상태라고 가정하고 문제를 접근하면, {A: 1, 1, 0, 1, 6}으로 생각해주면 된다.

코드는 다음과 같다:

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

using namespace std ; 

bool descending_order(int a, int b){
    return a > b ;
}

void set_input(vector<int> & v, int n){
    int temp ;
    for(int i = 0 ; i < n ; i++){
        cin >> temp ;
        v.push_back(temp) ;
    }
}

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(NULL) ; cout.tie(NULL) ;

    int N, s = 0 ;
    vector<int> A, B ;
    cin >> N ;

    set_input(A, N) ;    set_input(B, N) ;

    sort(A.begin(), A.end()) ;      sort(B.begin(), B.end(), descending_order) ;

    for(int i = 0 ; i < N ; i++)
        s += A[i] * B[i] ;
    
    cout << s << endl ;
    return  0 ;
}

해당 문제는 Github에서도 보실 수 있습니다.

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P1026_Treasure.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.