[백준] 1744 수 묶기 - Greedy / Java

• 문제 링크

1744번: 수 묶기

 

• 풀이 과정

수열의 합의 최대 값을 만들기 위해선 양수와 음수가 곱해져서 더 큰 음수를 만들지 않고,

음수와 음수끼리 곱하여 양수로 만들거나 0 와 음수를 곱하여 음수를 제거하여야 한다.

양수의 경우 내림차순으로 정렬하여 큰 순서대로 두 수를 곱하거나,

연산을 하는 두 수 중 1이 존재 할 시 두 수를 곱하는 대신 더한다.

 

따라서 양수는 양수끼리 연산하고, 음수는 0을 포함한 음수끼리 연산하여야 하므로 

서로 다른 List 객체 pn (positive number), nn (negative number) 에 따로 입력받아

각각의 연산의 결과를 sum 변수에 누적한다.

 

양수의 경우 두 수를 곱할 경우 범위에 벗어나지 않고, 두 수 중 1이 포함되지 않는 경우

후위 증가 연산자를 활용하여 곱연산하며, 나머지의 경우 곱할 두 수가 없으므로 sum 변수에 해당 값를 더한다.

 

음수는 범위를 벗어나지 않을 경우 오름차순으로 두 수를 곱연산하고 나머지는 sum 변수에 더한다.

 

이렇게 양수, 음수에서 연산된 값이 누적된 sum 변수를 정답으로써 출력한다.

 

• 풀이 코드

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.List;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		List<Integer> pn = new ArrayList<>();
		List<Integer> nn = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(br.readLine());
			if (num > 0)
				pn.add(num);
			else
				nn.add(num);
		}

		Collections.sort(pn, Collections.reverseOrder());
		Collections.sort(nn);

		int sum = 0;
		for (int i = 0; i < pn.size(); i++) {
			if (i + 1 < pn.size() && pn.get(i) != 1 && pn.get(i + 1) != 1)
				sum += pn.get(i++) * pn.get(i);
			else
				sum += pn.get(i);
		}

		for (int i = 0; i < nn.size(); i++) {
			if (i + 1 < nn.size())
				sum += nn.get(i++) * nn.get(i);
			else
				sum += nn.get(i);
		}

		bw.write(sum + "\n");
		bw.flush();
	}

}