백준 1744 수 묶기(java)

title : “백준 1744 수 묶기(java)”

Problem 1744

수 묶기

그리디 알고리즘, 정렬, 많은 조건 분기

문제

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

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

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

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

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 2^31보다 작다.

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

예제 입력 2

6
0
1
2
4
3
5

예제 출력 2

27

---

solve

• 아무 조합이나 곱할 수 있으므로 양수는 양수, 음수는 음수끼리 곱하는 것이 큰 수가 된다.
• 양수는 큰 수끼리 곱하는 것이 좋고, 1은 오히려 더하는게 좋다.
• 따라서 양수는 내림차순으로 곱하였고, 다음수가 1인지 확인하였다.
• 만약 수가 홀수이면 가장 작은 수는 그냥 더하므로 양수의 개수에 따라 조건을 걸어주었다.
• 음수도 비슷하지만 반대이다.
• 음수는 -1도 곱하면 양수가 되므로 무조건 곱하는게 좋다.
• 오름차순으로 정렬 후 곱하며 더해줬다.
• 만약 홀수인경우 남은 음수를 0과 곱할 수 있는지 확인했다.(0과 곱하면 0이 될 수 있으므로)

code

package week2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class boj1744 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		ArrayList<Integer> positiveNum = new ArrayList<Integer>();
		ArrayList<Integer> negativeNum = new ArrayList<Integer>();
		int zeroCnt = 0;
		int N = Integer.parseInt(br.readLine());

		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			if (num < 0) {
				negativeNum.add(num);
			} else if(num > 0){
				positiveNum.add(num);
			} else {
				zeroCnt++;
			}
		}
		Collections.sort(positiveNum, Collections.reverseOrder());
		Collections.sort(negativeNum);

		int sum = 0;
		if(positiveNum.size()%2 == 0) {
			
			for(int i=0; i<positiveNum.size(); i+=2) {
				if(positiveNum.get(i) == 1 || positiveNum.get(i+1) ==1) {
					sum += positiveNum.get(i) + positiveNum.get(i+1);
				} else {
					sum += (positiveNum.get(i) * positiveNum.get(i+1));
				}
			}
		} else {
			
			for(int i=0; i<positiveNum.size()-1; i+=2) {
				if(positiveNum.get(i) == 1 || positiveNum.get(i+1) ==1) {
					sum += positiveNum.get(i) + positiveNum.get(i+1);
				} else {
					sum += (positiveNum.get(i) * positiveNum.get(i+1));
				}
			}
			sum+=positiveNum.get(positiveNum.size()-1);
		}
		
		if(negativeNum.size()%2 == 0) {
			
			for (int i = 0; i < negativeNum.size(); i+=2) {
				sum += (negativeNum.get(i) * negativeNum.get(i+1));
			}
		} else {
			
			for(int i=0; i<negativeNum.size()-1; i+=2) {
				sum += (negativeNum.get(i) * negativeNum.get(i+1));
			}
			
			if(zeroCnt==0) {
				sum+=negativeNum.get(negativeNum.size()-1);
			}
		}
		
		bw.write(sum + "");
		bw.flush();
		bw.close();
		br.close();
	}
}