BOJ 1744번: 수 묶기

문제 설명

수열의 수를 2개씩 묶어서 나올 수 있는 최대 합 구하기

🔗 문제 링크

핵심 아이디어

• 양수는 내림차순 정렬 후 큰 것부터 곱하기
• 음수는 오름차순 정렬 후 작은 것부터 곱하기
• 1은 따로 관리하여 나중에 한 번에 더하기
• 0은 남는 음수에게 곱해서 없애기

코드

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    long long ans = 0;
    vector<int> plus;
    vector<int> minus;
    int zero = 0; int one = 0;
    
    for(int i = 0; i < n; i++){
        int a; cin >> a;
        if (a == 1) one++;
        else if (a > 0) plus.push_back(a);
        else if (a == 0) zero++;
        else if (a < 0) minus.push_back(a);
    }
    
    sort(plus.begin(), plus.end(), greater<int>());
    sort(minus.begin(), minus.end());
    
    if (plus.size() % 2 == 0){
        for(int i = 0; i < plus.size(); i +=2) ans += (plus[i]*plus[i+1]);
    }
    else{
        for(int i = 0; i < plus.size()-1; i +=2) ans += (plus[i]*plus[i+1]);
        ans += plus.back();
    }
    
    if (minus.size() % 2 == 0){
        for(int i = 0; i < minus.size(); i +=2) ans += (minus[i]*minus[i+1]);
    }
    else{
        for(int i = 0; i < minus.size()-1; i +=2) ans += (minus[i]*minus[i+1]);
        if (zero == 0){
            ans += minus.back();
        }
    }
    
    ans += one;
    
    cout << ans;
}

‼️ .back() vs .end()

.back()

• vector의 마지막 원소를 리턴
• 즉, vec[vec.size()-1]과 같은 것

.end()

• vector의 마지막 원소 다음을 가리키는 iterator
• 값이 아니라 위치를 나타냄