[Baekjoon] 2036_수열의 점수

Gold IV

문제(출처: https://www.acmicpc.net/problem/2036)

---

< 수열의 점수 >

 

문제 풀이 & 생각

 

단순 조건 분기를 활용해서 해결할 수 있는 문제였다. (0과 1이 존재할 때 조건 분기를 놓치지 않아야 한다.)

 

반례 조건

1) 1, 3이 있을 경우 1*3 < 1+3이다.

2) -8,0과 같이 0이 있으며 음수가 1개 있다면 -8*0 > -8+0이다.

 

또한, 1,000,000이 넘지 않는 정수가 입력으로 주어지므로 int 범위가 벗어나므로 long형을 사용해야 한다.

 

 my solution (Java)

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

public class _2036_ { // 수열의 점수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		long arr[] = new long[n];
		int neg = 0, zero = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = Long.parseLong(bf.readLine());
			if (arr[i] < 0)
				neg += 1;
			else if (arr[i] == 0)
				zero += 1;
		}

		Arrays.sort(arr);

		long result = 0;
		int idx = 0, pos = n - neg - zero;
		while (idx < n) {
			if (neg > 0) {
				if (neg == 1) {
					if (zero > 0) {
						zero -= 1;
						neg -= 1;
						idx += 2;
					} else {
						result += arr[idx];
						neg -= 1;
						idx += 1;
					}
				} else {
					result += arr[idx] * arr[idx + 1];
					idx += 2;
					neg -= 2;
				}
			} else if (zero > 0) {
				idx += zero;
				zero = 0;
			} else if (pos > 0) {
				if (arr[idx] == 1) {
					result += arr[idx];
					idx += 1;
					pos -= 1;
				} else if (pos % 2 == 0) {
					result += arr[idx] * arr[idx + 1];
					idx += 2;
					pos -= 2;
				} else {
					result += arr[idx];
					pos -= 1;
					idx += 1;
				}
			}
		}
		System.out.println(result);
	}
}

 

Main

변수)
n : 수열의 크기
arr : 수열 저장
neg, zero, pos: 음수, 0, 양수 개수
result: 최대 정수

 

- 수열의 크기 (n) 입력

- 수열 입력받은 후 저장한 배열 정렬

 

조건)

1) -8, 0과 같이 음수가 1개 있으며 0도 존재한다면 두 정수 제거, 0이 없다면 한 정수 제거

2) -8, -5와 같이 음수가 1개보다 많다면 두 정수 곱하면 양수가 되므로 두 정수 제거

3) 0이 여러 개 있다면 곱하거나 더하거나 0이므로 pass

4) 양수 중에서 1, 3과 같이 1이 있다면 1*3 < 1+3 이므로 1이 있을 때는 한 정수만 제거하여 1 제거하기

5) 1을 다 제거한 후 양수가 짝수개 있다면 두 정수 제거 but  2, 3, 5와 같이 홀수개 있다면 작은 수를 하나 제거하고 나머지를 두 개씩 곱하는 것이 큰 수를 얻을 수 있으므로 한 정수 제거

 

- 최대 점수(result) 출력

 

---

---