백준 1744 <수묶기>

이 문제의 핵심은 어떻게 수를 묶을 것인가이다. 

 

핵심을 파악하자면

음수는 음수끼리 양수는 양수끼리 묶는 게 결괏값이 더 커진다.

 

문제 접근 방법

1. 음수는 음수끼리 양수는 양수 끼리 묶는다
2. 가장 작은 음수는 그 다음 작은 음수와 묶는 것이 크고, 음수에 0을 곱하면 0 이 되기 때문에 이것 또한 작다.
3. 양수는 가작 큰 양수와 그 다음 큰 양수를 묶으면 값이 커진다. 하지만 0을 곱하면 안 된다. 또한 1을 곱하면 자기 자신이기 때문에 1은 곱해주지 않고 그냥 더한다. 
4. 그래서 정렬을 해서 음수는 앞에서부터 양수는 뒤에서부터 계산을 해주면 된다.

 

음수 계산 방법

양수 계산 방법

 

2

1

2

답: 3

 

5

1

1

1

1

1

답: 5

 

이 반례들을 통해 1은 양수랑은 곱하지 않는것이 좋다는것을 이해했다!!

 

전체 코드

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

public class Main {

	static int n, num[], result = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		num = new int[n];
		for (int i = 0; i < n; i++) {
			int next = Integer.parseInt(br.readLine());
			num[i] = next;
		}
		Arrays.sort(num);// num[i+1]<=0
		for (int i = 0; i < n; i++) {
			if (num[i] <= 0) {
				if(i==n-1) {
					result += num[i];
				}
				else if (num[i + 1] <= 0) {
					result += (num[i] * num[i + 1]);
					i++;
				} else
					result += num[i];
			} else {
				break;
			}
		}
		for (int i = n-1; i >=0 ; i--) {
			if (num[i] > 0) {
				if(i==0) {
					result += num[i];
				}
				else if (num[i - 1] > 1) {
					result += (num[i] * num[i - 1]);
					i--;
				} else
					result += num[i];
			} else {
				break;
			}
		}
		System.out.println(result);
	}

}