[코딩테스트 C++] 수 묶기

오늘의 문제

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

수 묶기

접근 법

• 자연수만 나왔다면 정렬해서 큰 수부터 2개씩 곱한값이 더 크면 더하고 아님 둘다 더하고, 개수가 홀수일 경우 마지막은 그냥 더해주는 방식을 하면 되는데
• 이 문제는 0과 음수도 있다.
• 양수, 음수를 따로 배열에 저장해서 각자 정렬을 한다. 0은 음수에 넣어준다.
• 양수는 곱한값이 원래 수보다 더 큰가를 검사해서 더 크면 곱한값을 더하고 아니면 각각 더한다.
• 개수가 홀수일 경우에는 마지막 값을 그냥 더한다.
• 음수는 곱한값이 무조건 크므로, 두개씩 곱한다. 그리고 마지막 값을 뺀다.
• 여기서 중요한점은 음수배열에 0을 넣어주는것. 0이 들어가면 음수와 곱한값이 0이 되므로 음수보다 큰 값을 가진다.

나의 풀이

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int sizeF =0, sizeS=0;
const int MAX = 10000;
int arr[MAX];
int arrm[MAX];

// 수 묶기
int solution(){
    int answer = 0;
    // 양수
    sort(arr, arr+sizeF);
    for(int i=0;i<sizeF-1;i+=2){
        int idx = sizeF -1 - i;
        if(arr[idx-1] * arr[idx] <= arr[idx]){
            answer += arr[idx] + arr[idx-1];
        }else{
            answer += arr[idx] * arr[idx-1];
        }
    }
    if(sizeF % 2 == 1) answer += arr[0];
    
    // 음수
    sort(arrm, arrm+sizeS);
    for(int i=0;i<sizeS-1;i+=2){
        int idx = sizeS -1 - i;
        answer += arrm[idx] * arrm[idx-1];
    }
    if(sizeS % 2 == 1) answer -= arrm[0];
    
    return answer;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>> n;
    int a;
    for(int i=0;i<n;i++){
        cin>>a;
        if(a <= 0) arrm[sizeS++] = -a;
        else arr[sizeF++] = a;
    }
    cout<< solution()<<endl;
    return 0;
}

다른 풀이

#include<cstdio>
#include<algorithm>
using namespace std;
int a[10000],n,r;
int main() {
	scanf("%d", &n);
	int i, j;
	for (i = 0; i < n; i++) scanf("%d", a + i);
	sort(a, a + n);
	for (i = 0; i < n - 1 && a[i + 1] < 1; i += 2) r += a[i] * a[i + 1];
	for (j = n - 1; j&&a[j - 1] > 1; j -= 2) r += a[j] * a[j - 1];
	for (; i <= j; i++) r += a[i];
	printf("%d", r);
	return 0;
}

배울 점

• 아 이사람은 배열을 따로 나누지않고, 1이상이 될때까지는 앞에서 뒤로, 그 위로는 뒤에서 앞으로 진행한다.
• 이런 배열을 나눠서 정렬한다고만 생각했는데 생각을 바꿔보면, 진행하는 방향만 다른것이다. 또 배워간다.