[BOJ 1744] 수 묶기 (Java)

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BOJ_Main_1744 {
	static int N;
	static List<Integer> plus=new LinkedList<>();
	static List<Integer> minus=new LinkedList<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		for (int i=0; i<N; i++) {
			int n=Integer.parseInt(br.readLine());
			if (n>0) plus.add(n);
			else minus.add(n);
		}
		Collections.sort(plus);
		Collections.sort(minus, Collections.reverseOrder());
		int sum=0;
		if (plus.size()%2!=0) {
			sum+=plus.get(0);
			plus.remove(0);
		}
		for (int i=plus.size()-1; i>=0; i-=2) {
			sum+=Math.max((plus.get(i)*plus.get(i-1)), (plus.get(i)+plus.get(i-1)));
		}
		if (minus.size()%2!=0) {
			sum+=minus.get(0);
			minus.remove(0);
		}
		for (int i=minus.size()-1; i>=0; i-=2) {
			sum+=Math.max((minus.get(i)*minus.get(i-1)), (minus.get(i)+minus.get(i-1)));
		}
		System.out.println(sum);
	}

}

처음엔 아무 생각없이 DFS 로 풀었다가 시간초과.. 당연한 결과다.. 거의 (O(n^n) 정도 나오니까..)

잘 생각해보니 그리디로 접근해야 되는 것을 깨달았다.

나의 풀이법은, 

minus-0부터 음수까지 내림차순으로 정렬된 리스트

plus-자연수가 오름차순으로 정렬된 리스트

 

로 해두고, 절댓값이 큰 수부터 시작해, 서로 인접한 것들끼리 곱해줘야 최댓값이 나온다는 아이디어를 뽑아내는게 중요했다.

 

리스트의 길이가 홀수일 경우, 쌍으로 곱해지지 않는 애들이 있다는 뜻이므로 이들은 모두 더해주고 리스트에서 삭제한다. 

리스트의 길이를 모두 짝수로 만든 뒤, 인접한 것들을 곱하거나 더한 값 중에 최댓값을 선택해 sum에 포함시키면 된다.

 

다른 분들의 코드를 보니(https://jaimemin.tistory.com/723 님),

1인 경우=> 무조건 더해줌.

양수가 저장되어 있는 리스트의 길이가 홀수일 경우=>1을 더해줘서 쌍을 만들어준다(더하는 효과)

음수 리스트의 길이가 홀수일 경우=>0이 있을 경우 0을 리스트에 더해줘소 최댓값을 만든다.

0이 없을 경우 1을 더해줘서 쌍이 만들어지지 않는 숫자를 더하는 효과를 낸다.

 

이렇게 처리를 한 뒤 두 수를 곱해주면 최댓값이 나온다.