03.12. 수 묶기 [Greedy Algorithm][백준 1744]

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

1744번: 수 묶기

 

Algorithm classification : Greedy Algorithm

 

03.12.1. Problem

Given a sequence of length N, we want to find the sum of the sequences. However, instead of just adding up the sum of the sequences, we are trying to combine two numbers in the sequence. When trying to group a number, it can be grouped regardless of its location. However, it is impossible to group numbers (self) in the same position. And when certain numbers are grouped together, when calculating the sum of a sequence, the grouped numbers are multiplied together and then added.

For example, if a sequence is {0, 1, 2, 4, 3, 5}, simply summing the sequence is 0+1+2+4+3+5 = 15. However, if 2 and 3 are tied together and 4 and 5 are tied together, 0+1+(2*3)+(4*5) = 27, which is the maximum.

All numbers in a sequence must be bound only once or not.

Given a sequence, write a program that maximizes the sum of each number in the sequence when properly grouped.

 

03.12.2. Input limit

The first line gives the size N of the sequence. N is a natural number less than 50. Each number in the sequence is given in N lines from the second line. The number of a sequence is an integer greater than or equal to -1,000 and less than or equal to 1,000.

 

03.12.3. Output

When the numbers are grouped together so that the sum is the maximum, the sum is printed. The correct answer is always less than 2^31.

 

03.12.4. Solution

모르겠어요. 저도 이 문제를 왜 풀었는지 그냥 심심해서 풀었나 봅니다. 백준 채점 현황을 보다가 있길래 그냥 풀어본 것 같습니다. Greedy 문제 같길래 포스팅해봅니다.

 

그닥 유쾌한 풀이는 아니군요.

int n, i, c1 = 0, c2 = 0, c3 = 0;
	scanf("%d", &n);
	int a[n];
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
		if(a[i] < 0) c1++;
		if(a[i] > 0) c2++;
		if(a[i] == 0) c3++;
	}
	
	sort(a, a + n);
	/*
	for(i = 0; i < n; i++){
		printf("%d ", a[i]);
		
	}
	printf("\n\n");
	*/
	
	
	
	int sum = 0;
	for(i = 0; i < n; i++){
		if(c1 > 1){
			sum += a[i] * a[i+1];
			c1 -= 2;
			i++;
		}
		else if(c1 == 1){
			if(c3 > 0){
				c3--;
				c1--;
				continue;
			}
			sum += a[i];
			c1--;
		}
		else{
			if(a[i] == 0){
				continue;
			}
			else if(a[i] == 1 || c2 % 2){
				sum += a[i];
				c2--;
			}
			else{
				sum += a[i] * a[i+1];
				c2 -= 2;
				i++;
			}
		}
		//printf("%d %d %d// ", sum, c1, c2);
	}
	printf("%d", sum);
	
	return 0;

 

 

많은 test case를 넣어보시는 것을 추천드립니다. 저도 몇개 남겨 놓겠습니다.

5
-5 -2 -3 0 0
>> 15

3 
1 1 0
>> 2

13
-10 -9 -8 -7 -6 -5 1 2 3 4 5 6 7
>> 245

10
-5 -4 -3 0 1 2 3 4 5 6
>> 65

10
-10 -9 -8 -7 -6 0 1 2 3 4
>> 161

5
-1 -2 0 0 0
>> 2

5
-5 -4 -3 -2 -1
>> 25