[백준 #1744] 수 묶기

백준 #1744 수 묶기

백준 #1744

---

문제 설명👩‍🏫

어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2 x 3)+(4 x 5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 최대 합을 return 해라.

입출력 예

입력
4
-1
2
1
3

출력
6

---

내 코드💻

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        int num = Integer.parseInt(str);
        ArrayList<Integer> plusList = new ArrayList<>();
        ArrayList<Integer> minusList = new ArrayList<>();

        int sum = 0;
        boolean check0 = false;

        for(int n=0;n<num;n++){
            str = br.readLine();
            int i=Integer.parseInt(str);
            if (i==0){
                check0 = true;
            }
            else if(i==1){
                sum+=1;
            }
            else if (i<0){
                minusList.add(i);
            }
            else{
                plusList.add(i);
            }
        }

        boolean minusSize = minusList.size() % 2 == 0 ? true:false;
        boolean plusSize = plusList.size() % 2 == 0 ? true:false;

        Collections.sort(minusList);
        Collections.sort(plusList, Collections.reverseOrder());


        if(!minusSize){
            if(!check0) {
                sum += minusList.get(minusList.size()-1);
            }
            minusList.remove(minusList.size()-1);
        }
        if(!plusSize){
            sum += plusList.get(plusList.size()-1);
            plusList.remove(plusList.size()-1);
        }

        while(!minusList.isEmpty()){
            int num1 = minusList.get(0);
            int num2 = minusList.get(1);

            sum += num1 * num2;
            
            minusList.remove(0);
            minusList.remove(0);
        }
        while(!plusList.isEmpty()){
            int num1 = plusList.get(0);
            int num2 = plusList.get(1);

            sum += num1 * num2;
            
            plusList.remove(0);
            plusList.remove(0);
        }

        System.out.println(sum);
    }
}

---

설명💡

이 문제에서는 0과 1을 어떻게 다루냐가 중요한 것 같았다.
음수는 0과 곱하면 없어질수도, 음수끼리 곱하면 오히려 커질수도 있고, 1은 곱하기 보단 더하기가 더 큰 수를 만들 수 있기 때문이다.

---

그래서 처음 입력받을 때, 0이 있냐 없냐를 체크, 1은 최종 답에 바로 더하고, 나머지 음수와 양수는 각각의 list에 나눠서 넣었다.
그리고 각각의 list는 오름차순, 내림차순으로 정렬해준다.
minusSize와 plusSize는 각각의 list들의 크기가 홀수인지 짝수인지 확인하기 위해 사용했다.
만약 홀수개라면 각각의 마지막 원소는 그냥 바로 답에 더해주면 된다. 만약 0이 존재하고, 음수가 홀수개라면, 음수의 가장 마지막 원소는 0으로 바꿔줄수 있다.

---

그리고 나서 짝수개인 각각의 list들을 앞에서부터 2개씩 꺼내 곱한 값을 답에 더해주면 된다.

---

느낀 점 및 궁금한 점🍀

생각해야 할 부분들이 많은 문제였던 것 같다..🫥 처음에는 if문도 되게 더럽게(?) 쓰고 그랬는데, 계속 수정하면서 최대한.. 보기 편하게 만들었다..