[BOJ] 1744. 수 묶기(그리디).java

#. Problem

www.acmicpc.net/problem/1744

* The copyright in this matter is in acmicpc

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

예외 처리해줘야 하는 부분이 있어서 생각보다 까다로웠다.

그리디 문제는 알고 나면 허무한데 그 과정이 간혹 두뇌를 무리하게 한다...

 

본론으로 가보자.

 

* 숫자는 최대한 두 개씩 묶이는 게 이득이다. (양수에서는 큰 값 두 개씩, 음수에서는 작은 값 두 개씩)

    - 양수, 음수 각각 홀수개일 경우 처리 -> 양수는 그냥 더해주고, 음수는 그나마 큰 값을 더해줘야 한다.

* 0 과 1 처리 -> 0은 가장 작은 음수와 곱하고 1은 그냥 더해주는 게 이득

 

추가로,

질문 게시판에 kimdh425 님이 공유해주신 글을 참고하면 좋을 것 같다.

 

case1. 양수 기준 - (양수가 짝수개일 때) 내림차순으로 정렬했을 때 큰 값 2개씩 곱해서 답을 도출하는가
case 2. 양수 기준 - (양수가 홀수개일 때) 내림차순으로 정렬했을 때 큰 값 2개씩 곱한 후 마지막에 숫자를 더해서 답을 도출하는가
case 3. 음수 기준 - 오름차순으로 정렬했을 때 작은 값 2개씩 묶어서 답을 도출하는가 (이유 : 음수는 작을수록 두 수를 곱했을 때 커지므로)
case4. 0이 존재하면서 음수의 개수가 홀수개 일 때 마지막 음수를 0으로 처리하는지
case5. 1이 존재할때 1은 다른 수와 곱하지 않고 바로 더하는지 (이유 : 1보다 큰 수 x와 1이 주어진다면 두 수를 곱하는 것보다 따로 더해주는 게 더 크다)

#. Code

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

public class Main {
	
	static int N;
	static List<Integer> plus, minus;
	static boolean hasZero = false;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		plus = new ArrayList<>();
		minus = new ArrayList<>();
		for (int i = 1; i <= N; i++) {
			int tmp = Integer.parseInt(br.readLine());
			if (tmp < 0) minus.add(tmp);
			else if (tmp == 0) hasZero = true;
			else plus.add(tmp);
		}
		// 양수는 내림차순
		plus.sort(Comparator.reverseOrder());
		// 음수는 오름차순
		minus.sort(null);
		
		System.out.println(process());		
	}

	private static int process() {
		int res = 0, size = plus.size();
		
		// 양수
		for (int i = 0; i < size - 1; i+=2) {
			// 1일 경우 각각 더하는게 이득
			if(plus.get(i) == 1 || plus.get(i+1) == 1) {
				res += plus.get(i) + plus.get(i+1);	
			} else {
				res += plus.get(i) * plus.get(i+1);
			}
		}
		// 양수가 홀수개 있을 경우 나머지 처리
		if (size % 2 != 0) res += plus.get(size - 1);
		
		// 음수
		// 0이 있을 경우 처리
		if (hasZero) {
			// 음수가 홀수개일 경우
			if(minus.size() % 2 == 1) size = minus.size() - 1;
			else size = minus.size();
		} else { 
			size = minus.size(); 
		}
		for (int i = 0; i < size - 1; i+=2) { 
			res += minus.get(i) * minus.get(i+1);
		}
		// 음수가 홀수개 있을 경우 나머지 처리
		if (size % 2 != 0) res += minus.get(size - 1);
		
		return res;
	}
}

#. Code_optimization

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	
	static int N;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			int tmp = Integer.parseInt(br.readLine());
			arr[i] = tmp;
		}
		Arrays.sort(arr);
		
		System.out.println(process());		
	}

	private static int process() {
		int res = 0, i;
		
		// 음수(작은 값부터 곱하기) 
		for (i = 0; i < N && arr[i] < 0; i+=2) {
			// 다음 수가 음수 or 0일 경우 곱해주자.
			if (i + 1 < N && arr[i + 1] <= 0) {
				res += arr[i] * arr[i+1];
			} else {
				// 음수가 홀수개일 경우
				res += arr[i];
				break;
			}
		}
		
		for (i = N - 1; i >= 0 && arr[i] > 1; i -= 2) {
			// 다음 수가 양수일 경우 곱해주자.
			if (i > 0 && arr[i - 1] > 1) {
				res += arr[i] * arr[i-1];
			} else {
				// 양수가 홀수개 있거나 1일 경우
				break;
			}
		}		
		
		// 남은 숫자 더해주기
		while (i >= 0 && arr[i] > 0) {
			res += arr[i]; 
			i--;
		}
				
		return res;
	}
}