백준 1744 수 묶기 쉬운 풀이(C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1744

 

문제 접근

• 숫자끼리 더하거나 곱해서 최대로 나올수 있는 방법이 있음 >> 그리디
  • 양수 : 큰수는 큰수끼리 곱해야함
  • 음수 : 큰 음수끼리 곱해야함
  • 0 :
    • 음수가 짝수일때 >> 그냥 더함
    • 음수가 홀수일때 >> 음수에 곱함
      • 예외 케이스
  • 1곱하기 1인경우 >> 그냥 더하는게 나음
  • -1곱하기 -1은 >> 곱하는게 나음

시간복잡도 계산

• 정렬한뒤 순차탐색 >> O(NlgN + N) >> O(NlgN) >> 20 * e5 = 2e6

 

인트 계산

• 정답은 항상 2^31 보다 작음 >> Int 가능?
• 근데 연산하는 중 수가 더 커질수도 있음
  • 예시 : e4 * e4 가 5000쌍일경우
  • 그래서 안전하게 long long으로

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll nums[10010];
int main() {
    int N; cin >> N;
    int cntY=0, cntU=0, cnt1=0;
    for(int i=0; i<N; i++) {
        cin >> nums[i];
        if(nums[i] >1) cntY++;
        else if(nums[i] == 1) cnt1++;
        else if(nums[i] < 0) cntU++;
    }
    
    sort(nums, nums+N);
    ll rs=0;
    // 양수끼리 곱함
    bool sw = 0;
    ll tmp=0;
    for(int i=N-1; i>=N-cntY; i--) {
        // 양수 처음 더하면
        if(sw == 0) {
            sw = 1;
            tmp = nums[i];
        } else {
            sw = 0;
            rs += nums[i] * tmp;
            tmp = 0;
        }
    }
    
    if(sw == 1) {
        rs += tmp;
        tmp = 0;
        sw = 0;
    }
    rs += cnt1;
    
    sw = 0;
    tmp = 0;
    
    //음수끼리 곱함
    for(int i=0; i<N-cntY-cnt1; i++) {
        // 음수 처음이면
        if(sw == 0) {
            sw = 1;
            tmp = nums[i];
        } else {
            sw = 0;
            rs += nums[i] * tmp;
            tmp = 0;
        }
    }
    
    if(sw == 1) {
        // 만약 zero 있으면 더해서 0이므로 끝
        // 없으면 그냥 더함
        if(N == cntY + cntU + cnt1) {
            rs += tmp;
        }
        
    }
    
    cout << rs << '\n';
    
    
    return 0;
}
 

 

문제유형

• 그리디 - 숫자관련 최소 최대