백준 1744 (수 묶기)

문제

---

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

 

 

 

풀이

---

그리디알고리즘은 어느때와 같이 경우의 수를 정렬해야한다.

 

1. 같은 부호의 수를 곱하면 절댓값은 커진다는것.

• 양수 * 양수
• 음수 * 음수

2. 숫자 0은 어떤 수를 곱해도 0이 된다. 이는 음수와 곱해지면 좋을 것이다.

• 음수 * 0

3. 1은 곱하기 보다 더해주는것이 좋다.

• 2*1 = 2 // 2+1 = 3

이 세가지 경우의 수를 이용해서 문제를 풀었다.

1. 우선 숫자를 1, (1을 제외한 양의 정수), (0 과 음의 정수) 이 세가지로 경우를 나누어서 저장한다.
2. 1 은 바로 더해준다.
3. 양의 정수가 들어있는 배열은 내림차순정렬을 한다.
4. 음의 정수가 들어있는 배열은 오름차순정렬을 한다.(음수는 절댓값이 클수록 크기가 작아지기 때문)
5. 양의 정수를 앞에서 부터 차례대로 2개씩 짝을 지어 곱해준뒤 더해준다.
6. 음의 정수와 0이 들어있는 배열을 앞에서 부터 차례대로 2개씩 짝을지어 곱해준 뒤 더해준다.

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	static int Multiple(int a, int b) {
		
		return a * b;
	}
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		int n = Integer.parseInt(br.readLine());
		
		List<Integer> positive = new ArrayList<Integer>();
		List<Integer> negative = new ArrayList<Integer>();
		int total = 0;
		for(int i = 0 ; i < n ; i++) {
			int num = Integer.parseInt(br.readLine());
			if(num > 1 ) {
				positive.add(num);
			}
			else if(num == 1) {
				total += num;
			}
			else {
				negative.add(num);
			}
		}
		
		//양수는 내림차순
		Collections.sort(positive, Comparator.reverseOrder());
		//음수는 오름차순
		Collections.sort(negative);
		
		int temp = 0;
		
		for(int i = 0 ; i < positive.size() ; i++) {
			temp = positive.get(i);
			if(i < positive.size() - 1) {
				temp = Multiple(positive.get(i), positive.get(i + 1));
				i++;
			}
			
			total += temp;
		}
		
		for(int i = 0 ; i < negative.size(); i++) {
			temp = negative.get(i);
			if(i < negative.size() - 1) {
				temp = Multiple(negative.get(i), negative.get(i + 1));
				i++;
			}
			
			total += temp;
		}
		
		System.out.println(total);
	}
}