[cpp 알고리즘] 백준 1744 수 묶기

[백준] 1744 수 묶기 풀이

그리디 알고리즘, 정렬, 많은 조건 분기

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

문제 요약

- 길이가 N인 수열이 주어졌을 때, 두 수를 곱하거나 그대로 둘 수 있다. 이 수들을 모두 더한 값들 중 최댓값을 구하면 된다. 

풀이 정리

1. 일단 오름차순으로 정렬한다.

2. 숫자 1을 기준으로 3가지 경우로 나뉘어진다.

    (1) 1보다 작은, 0이거나 음수인 경우 -> 앞쪽(작은 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다. 

    (2) 1인 경우 -> 곱하는 데 사용하지 않고, 더하면 된다.

    (3) 1보다 큰 양수인 경우 -> 뒤쪽(큰 수)부터 두 수를 곱해서 최종 결과 값에 더하면 된다.

3. (1)의 경우 혹은 (3)의 경우가 홀수개여서 남는 숫자들은 따로 더해주면 된다. 

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[51];

int main(){
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> arr[i];
    
    int left = 0, right = N-1;
    sort(arr, arr+N);
    
    int ans = 0;
    
    // 0이거나 음수인 경우
    for (; left < right; left += 2){
        if (arr[left] < 1 && arr[left+1] < 1){
            ans += (arr[left] * arr[left+1]);
        }
        else{
            break;
        }
    }
    
    // 양수인 경우
    for (; right > 0; right -= 2){
        if (arr[right] > 1 && arr[right-1] > 1){
            ans += (arr[right] * arr[right-1]);
        }
        else{
            break;
        }
    }
    
    for (; right >= left; right--){
        ans += arr[right];
    }
    
    cout << ans;
    
    return 0;
}

기타

백준 1744 풀이