[BOJ] 1744 : 수 묶기 (Java)

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

1744번: 수 묶기

걸린 시간 : 25분 2초

---

알고리즘

두 수를 묶는다는 것은 곱한다는 것이다. 따라서 음수끼리 혹은 양수끼리 곱해야 한다.

즉, 음수가 짝수라면 작은 음수부터 차례대로 묶어가면 끝이다. 양수도 마찬가지로 짝수라면 큰 수부터 차례대로 묶어가면 된다.

만약 양수가 홀수라면 가장 작은 양수를 묶지 않고 즉시 더해주면 된다.

만약 음수가 홀수라면 가장 큰 음수를 즉시 더해주면 된다. 단, 만약 수열에 0이 존재할 경우 이 수는 0과 묶어서 날려버릴 수 있다.

 

여기까지는 많은 사람들이 생각했을 것이지만, 예상치 못한 부분이 하나 있었다. 양수에 1을 곱하면 자기 자신이 되어 커지지 않는다는 것이다. 즉 어떤 두 양수를 묶으면 (곱하면) 무조건 그 결과가 두 양수를 묶지 않았을 때보다 (더했을 때보다) 클 것이라고 예상했지만, 1이 존재하면 더하는 것이 더 큰 것이다.

따라서 수열을 입력받을 때, 1이 들어온다면 무조건 즉시 답에 1을 더해주고 배열에 넣지 않는다.

정답 코드

import java.io.*;
import java.util.*;

public class BOJ1744 {

    static int N;
    static List<Integer> negArr = new ArrayList<>();
    static List<Integer> posArr = new ArrayList<>();
    static boolean existZero = false;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(br.readLine());
            if (tmp == 1) {
                answer++;
            } else if (tmp < 0) {
                negArr.add(tmp);
            } else if (tmp > 0) {
                posArr.add(tmp);
            } else {
                existZero = true;
            }
        }
        Collections.sort(negArr);
        posArr.sort(Collections.reverseOrder());
        if (negArr.size() % 2 == 1) {
            if (!existZero) {
                answer += negArr.get(negArr.size()-1);
            }
            negArr.remove(negArr.size()-1);
        }
        if (posArr.size() % 2 == 1) {
            answer += posArr.get(posArr.size()-1);
            posArr.remove(posArr.size()-1);
        }
        for (int i = 0; i < negArr.size(); i += 2) {
            answer += negArr.get(i) * negArr.get(i+1);
        }
        for (int i = 0; i < posArr.size(); i += 2) {
            answer += posArr.get(i) * posArr.get(i+1);
        }
        System.out.println(answer);
    }
}