boj-1744 수 묶기

1744번: 수 묶기

 

 

 

 

 

 

풀이

---

반례 때문에 조금 고생했던 문제인데요, 케이스별로 묶는 것이 핵심인 문제였습니다. 이때 기준을 1로 삼아야 하는데요, 1은 다른 수와 곱하면 자기 자신이 나오기 때문에 무조건 더해주어야 하기 때문입니다. 따라서 1 미만일 경우, 1일 경우, 1초과일 경우로 이를 각각 분류해준 뒤 두 개씩 묶어서 더해주면 됩니다. 이때 개수가 짝수/홀수인 경우도 고려해줘야 하는데, 홀수인 경우 두개씩 묶고나서 마지막 수를 더해주면 됩니다. 

 

public class Main {
    public static void main(String[] args) throws Exception {
        int n = input.integer();
        List<Integer> plus = new ArrayList<>();
        List<Integer> others = new ArrayList<>();
        List<Integer> minus = new ArrayList<>();

        for (int index = 0; index < n; index++) {
            int number = input.integer();
            if (number > 1) {
                plus.add(number);
                ;
            } else if (number == 1) {
                others.add(number);
            } else {
                minus.add(number);
            }
        }
        
        Collections.sort(plus, Collections.reverseOrder());
        Collections.sort(others);
        Collections.sort(minus);

        int sum = 0;

        if (plus.size() != 0) {
            if (plus.size() % 2 != 0) {
                for (int index = 0; index < plus.size() - 1; index += 2) {
                    sum += plus.get(index) * plus.get(index + 1);
                }
                sum += plus.get(plus.size() - 1);
            } else {
                for (int index = 0; index < plus.size(); index += 2) {
                    sum += plus.get(index) * plus.get(index + 1);
                }
            }
        }
        
        if (others.size() != 0) {
            for (int index = 0; index < others.size(); index++) {
                sum += others.get(index);
            }
        }
        
        if (minus.size() != 0) {
            if (minus.size() % 2 != 0) {
                for (int index = 0; index < minus.size() - 1; index += 2) {
                    sum += minus.get(index) * minus.get(index + 1);
                }
                sum += minus.get(minus.size() - 1);
            } else {
                for (int index = 0; index < minus.size(); index += 2) {
                    sum += minus.get(index) * minus.get(index + 1);
                }
            }
        }
        System.out.println(sum);


    }

    static Input input = new Input();

    static class Input {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public int integer() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return Integer.parseInt(st.nextToken());
        }

        public String next() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public char[] nToCharArray() throws Exception {
            if (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
            return st.nextToken().toCharArray();
        }
    }
}