[Greedy] 백준 1744번 "수 묶기" C++ 풀이

문제 링크

• https://www.acmicpc.net/problem/1744

풀이

• 최댓값을 유도하기 위해선
  • 양수와 음수는 서로 곱해야한다.
    • 양수 묶음의 경우, 큰 수끼리 곱해야한다. (ex. 5, 4)
    • 음수 묶음의 경우, 절대값이 큰 음수끼리 곱해야한다. (ex. -5, -4)
  • 1 은 어떠한 경우든, 묶어서 곱셈하는 결과값보다, 개별로 덧셈하는 결과값이 더 크다.
  • 0 을 개별로 더하는 것은 무의미하므로,
  • 음수의 개수가 홀수일 경우, 가장 절대값이 작은 음수와 0 을 곱해주는 방식이 최댓값 유도에 좋다. (ex. -1 * 0)
• 풀이 방법
  • 양수들은 positive 벡터에 저장하고, 음수들은 negative 벡터에 저장한다.
  • 0 의 개수는 개별 변수로 저장하고, 1 은 모두 총 결과값에 더해준다.
  • 이후, positive 벡터는 내림차순 정렬하고, negative 벡터는 오름차순 정렬한다.
  • positive 벡터의 요소가 홀수개라면(4, 3, 2), 앞에서부터 2개씩 묶어 곱셈한 결과와 가장 작은 값을 총 결과값에 더해준다.
  • negative 벡터의 요소가 홀수개라면(-5, -4, -3), 앞에서부터 2개씩 묶어 곱셈한 결과를 총 결과값에 더한 뒤,
  • 0 이 존재한다면 negative 벡터의 가장 큰 값(-3)과 곱해 음수를 상쇄시키고,
  • 0 이 존재하지 않는다면 negative 벡터의 가장 큰 값(-3)을 바로 총 결과값에 더한다.
• 예시
  • [-4, 1, -3, 1, -1, 0, 5, 1, 2] 가 입력으로 들어올 경우 아래와 같이 구분할 수 있다.
    • 양수 : 5, 2
    • 1, 1, 1
    • 0
    • 음수 : -4, -3, -1
  • 따라서, 아래와 같이 최대값을 도출할 수 있다.
    • (5 * 2) + 1 + 1 + 1 + ( 0 * -1 ) + (-3 * -4) = 25

코드

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

using namespace std;

// 양수 저장 벡터
vector<int> positive;

// 음수 저장 벡터
vector<int> negative;

// 0 의 개수
int zero_count;

// 수열 최댓값
int result;

// 수열 최댓값 출력 함수
int greedy(){

    // 양수 저장 벡터 내림차순 정렬
    sort(positive.begin(), positive.end(), greater<int>());
    // 음수 저장 벡터 오름차순 정렬
    sort(negative.begin(), negative.end(), less<int>());

    // 내림차순 정렬된 양수 저장 벡터의 요소들을 두 묶음씩 곱한 뒤, 결과값에 추가
    for (int i=0; i<positive.size()-(positive.size()%2); i +=2){
        // i 번째 요소와 i+1 번째 요소를 곱한 뒤, 결과값에 추가
        result += positive[i] * positive[i+1];
    }

    // 양수 저장 벡터가 홀수일 경우, 마지막 요소가 묶음에서 제외되었기 떄문에, 마지막 요소를 결과값에 추가
    if (positive.size() % 2 == 1){
        result += positive.back();
    }

    // 오름차순 정렬된 음수 저장 벡터의 요소들을 두 묶음씩 곱한 뒤, 결과값에 추가
    for (int i=0; i<negative.size()-(negative.size()%2); i +=2){
        // i 번째 요소와 i+1 번째 요소를 곱한 뒤, 결과값에 추가
        result += negative[i] * negative[i+1];
    }

    // 음수 저장 벡터가 홀수일 경우, 마지막 요소가 묶음에서 제외되었기 떄문에, 마지막 요소를 결과값에 추가
    if (negative.size() % 2 == 1){

        // 만약, 수열에 0 이 존재하지 않는다면, 음수 저장 벡터의 마지막 요소를, 그대로 결과값에 추가
        if (zero_count == 0){
            result += negative.back();
        }
        // 만약, 수열에 0 이 존재한다면, 음수 저장 벡터의 마지막 요소와 0 을 곱할 수 있으므로, 상쇄 가능   
    }

    // 수열 최댓값 반환
    return result;

}

int main(){

    // 수열의 개수
    int n;
    cin >> n;

    // 수열 요소 입력
    for (int i=0; i<n; ++i){
        int number;
        cin >> number;

        // 숫자가 1 보다 크다면, 양수 저장 벡터에 저장
        if (number >1){
            positive.push_back(number);
        }
        // 숫자가 1 이라면, 수열 최댓값에 추가
        else if (number == 1){
            result += 1;
        }
        // 숫자가 0 이라면, 0 의 개수 추가
        else if (number == 0){
            zero_count += 1;
        }
        // 숫자가 0 보다 작다면, 음수 저장 벡터에 저장
        else{
            negative.push_back(number);
        }
    }

    // 수열 최댓값 출력
    cout << greedy() << endl;

}

참고

• https://chosh95.tistory.com/160
• https://scarlettb.tistory.com/116