백준 수 묶기(Java) / Greedy 알고리즘

문제

---

길이가 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 : 모든 수는 단 한 번만 묶거나, 묶지 않아야 한다.

조건 3 : 그 합이 최대가 되어야 한다. 

 

내가 생각한 해결 방법

 

1 : 음수는 음수끼리, 양수는 양수끼리 묶었을 때, 그 값이 가장 크다.

2 : 0은 항상 음수와 곱해야 값이 크다.

3 : 1은 아무와도 묶지 않는다.

 

풀이 

음수와 양수를 구분하여 Linkedlist에 담은 후, 하나씩 poll함수로 꺼내어 곱한다. 

 

양수가 담긴 posi 리스트는 가장 큰 수부터 곱한 후 1이 있을 경우는 따로 더한다.

음수가 담긴 nega 리스트는 가장 작은 수부터 곱한 후에 0이 있을 경우 곱한다.

import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		LinkedList<Integer> posi = new LinkedList<Integer>();
		LinkedList<Integer> nega = new LinkedList<>();
		long sum = 0;
		for(int i=0; i<N; i++) {
			int tmp = sc.nextInt();
			if(tmp>0) posi.add(tmp);
			else nega.add(tmp);
		}
		Collections.sort(posi, Collections.reverseOrder());
		Collections.sort(nega);
		while(posi.size()>0) {
			int a = posi.poll();
			if(posi.isEmpty()) {
				sum += a;
				break;
			}
			int b = posi.poll();
			
			sum += Math.max(a+b, a*b);
		}
		
		while(nega.size()>0) {
			int a = nega.poll();
			if(nega.isEmpty()) {
				sum += a;
				break;
			}
			int b = nega.poll();
			
			sum += Math.max(a+b, a*b);
		}
		
		System.out.println(sum);
	}

}

 

다른 자료구조를 사용하거나 수학적 방법, 완전 탐색을 사용해도 충분히 풀 수 있는 문제이다.