[BOJ 1744 // C++] 수 묶기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1744번 문제인 수 묶기이다.

문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1744

1744번: 수 묶기

이 문제는 주어진 숫자를 둘씩 짝을 지어 곱해 더하거나 그냥 더해 최댓값을 얻는 것이 목표이다.

이때, 주어지는 숫자에는 양수도 음수도 있음에 유의하여야 한다.

 

이 문제의 풀이를 구상할 때 신경써야하는 점을 살펴보자.

 

1) 두 음의 정수의 곱은 양의 정수가 된다. 따라서 음의 정수가 여러 개 있다면 가장 작은(절댓값이 가장 큰) 두 수를 곱해 더해줘야한다.

2) 위와 같이 묶고 음의 정수가 1개 남았을 때 남은 정수 중 0이 있다면 음의 정수를 더하는 것보다는 음수와 0을 곱해 더해야 한다. 남는 0이 있다면 그냥 더해주면 된다. (음의 정수끼리 곱하여 양수를 만드는 것이 더 이득이기 때문)

3) 양의 정수들은 큰 수 2개끼리 묶어서 곱해나가야한다. 단, 1은 다른 수와 곱하지 말고 따로 더해야 한다.

 

위 내용을 신경쓰면서 다음과 같은 알고리즘을 구상하였다.

 

1) 입력을 받아 배열을 만든 후 크기순으로 정렬한다.

2) 배열의 왼쪽서부터 양이 아닌 정수를 크기순으로, 짝을 지을 수 없을 때까지 둘씩 묶어 곱해 더한다.

2-1) 짝을 짓지 못하고 남은 수는 그냥 더해준다.

3) 배열의 오른쪽서부터 1보다 큰 양의 정수를 크기순으로, 짝을 지을 수 없을 때까지 둘씩 묶어 곱해 더한다.

3-1) 짝을 짓지 못하고 남은 수는 그냥 더해준다.

4) 남은 수는 1 뿐이다. 1의 개수를 더해준다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
using std::sort;
using std::cin;
using std::cout;

int nums[10000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int x;
    int cntone = 0;
    for (int i = 0;i < n;i++) {
        cin >> x;
        nums[i] = x;
        if (x == 1) cntone++; // 1의 개수를 미리 세둔다
    }
    sort(nums, nums + n);
    int ans = 0;
    int leftpt = 0; // 배열의 왼쪽부터 살필 포인터
    int rightpt = n - 1; // 배열의 오른쪽부터 살필 포인터
    if (n == 1) cout << nums[0]; // 예외처리 -  배열의 크기가 1인 경우
    else {
        while (nums[leftpt + 1] < 1) { // 양이 아닌 정수들을 크기순으로 짝지어 곱해 더하기
            ans += nums[leftpt] * nums[leftpt + 1];
            leftpt += 2;
            if (leftpt == n - 1 or leftpt == n) break; // 예외처리 - 배열의 모든 정수가 음수인 경우
        }
        if (leftpt < n) { // 짝을 짓지 못하고 남은 양이 아닌 정수를 더하기
            if (nums[leftpt] < 1) ans += nums[leftpt];
        }
        while (nums[rightpt - 1] > 1) { // 1보다 큰 양의 정수들을 크기순으로 짝지어 곱해 더하기
            ans += nums[rightpt] * nums[rightpt - 1];
            rightpt -= 2;
            if (rightpt == 0 or rightpt == -1) break; // 예외처리 - 배열의 모든 정수가 양수인 경우
        }
        if (rightpt >= 0) { // 짝을 짓지 못하고 남은 1보다 큰 양의 정수를 더하기
            if (nums[rightpt] > 1) ans += nums[rightpt];
        }
        ans += cntone; // 1을 개수만큼 더해주기
        cout << ans;
    }
    
    return 0;
}