c언어 1744번 수 묶기 (백준)

#include <stdio.h>

int main(void)
{
	int n, i, j, key;
	scanf("%d", &n);
	int a[n];
	int gap = n/2;
	
	for(i = 0; i<n; i++) scanf("%d", &a[i]);
	
	while(1) //shell sort
	{
		if(gap%2==0) gap++;
		for(i=gap; i<n; i++) {
			key = a[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key < a[j]) a[j+gap] = a[j];
				else break;
			} a[j+gap] = key;
		}
		if(gap==1) break;
		gap/=2;
	}
	
	int minus = 0; //음수 개수
	int zero = 0; //0 개수
	int one = 0; //1 개수
	long long int sum = 0; //종합
	for(i=0; i<n; i++) { //음수, 0, 1 개수 세기
		if(a[i] < 0) minus++;
		else if(a[i] == 0) zero++;
		else if(a[i] == 1) one++;
		else break;
	}
	
    //아래에서 말하는 양수는 1 초과의 양수입니다.
	for(i=0; i+1<minus; i+=2) sum += a[i] * a[i+1]; //음수 두개씩 곱하기
	if(minus%2==1) if(zero==0) sum+=a[minus-1]; //음수가 1개 남고, 0이 1개이상이면 서로 곱함
	for(i=n-1; i-1>=one+minus+zero; i-=2) sum += a[i]*a[i-1]; //양수 큰 것 부터 두개씩 곱하기
	if((n-(minus+zero+one))&1) sum += a[minus+zero+one]; //양수가 1개 남으면 그냥 더해줌
	sum += one; //1을 더해줌, 1은 곱하는게 손해다.
	printf("%lld", sum); 출력
}

 

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

1744번: 수 묶기

 

 

풀이 : 그리디 알고리즘

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

 

2. 음수의 개수, 0의 개수, 1의 개수를 구한다.

 

3. 음수는 서로를 곱해야 양수가 되며, 이를 절댓값이 큰 수부터 둘 씩 곱해주면, 최댓값이다.

 

4. 음수의 개수가 홀수 일 경우 마지막으로 음수는 1개가 남는다. 만약 0이 1개 이상이면, 0 하고 곱해주면 된다.

 

5. 1*n < 1+n (단 n>=1)이므로 1은 반드시 더해준다.

 

6. 2 이상의 양수들은 큰 순서대로 두개 씩 곱해준다. 만약 홀수이면, 마지막 하나는 더해준다.