[백준] 1744 수 묶기 - 그리디

문제 링크 : https://www.acmicpc.net/problem/2011

🍊해결방법

• 두 수를 곱하고 더했을 때 최대값이 되어야 하므로
• 양수는 양수끼리 음수는 음수끼리 곱해야 최대가 된다
• 0은 음수와 곱해야 더했을 때 유리
• 1은 곱하는 것보다 더하는게 유리하므로 묶지 않고 따로 개수만 count해서 마지막에 더해주자
• 양수끼리 list1과 음수끼리 list2를 담아서 양수는 내림차순, 음수는 오름차순으로 해야 곱했을 때 최대
• 각각의 사이즈가 짝수면 2개씩 곱해서 더하면 상관없지만 홀수일 경우 마지막을 더해줘야한다

😀풀이

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

public class Main {



    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 양수와 음수 서로 곱하는게 유리
        // 그러면 순서는 중요하지 않으니 양수 따로 음수 따로 저장하자
        // 1은 곱하는것보다 더하는게 유리 따로 빼서 나중에 더해주자
        // 0은 음수일때 곱하는게 유리

        int N = Integer.parseInt(br.readLine());

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        int cnt = 0;

        for(int i=0; i<N; i++){
            int num = Integer.parseInt(br.readLine());

            // 음수
            if (num <= 0){
                list2.add(num);
            }
            else if (num == 1){
                cnt++;
            }
            // 2이상 양수
            else{
                list1.add(num);
            }
        }

        // 음수는 오름차순으로
        Collections.sort(list2);

        // 양수는 내림차순으로
        Collections.sort(list1, Collections.reverseOrder());

        int ans = 0;

        int tmp1 = 1;
        for(int i=0; i<list2.size(); i++){
            // 두개 수
            if (i%2 == 1){
                tmp1 *= list2.get(i);
                ans += tmp1;
                tmp1 = 1;
            }
            else{
                tmp1 *= list2.get(i);
            }
        }
        // 남은 수
        if(tmp1 != 1)
            ans += tmp1;

        int tmp2 = 1;
        for(int i=0; i<list1.size(); i++){
            if (i%2 == 1){
                tmp2 *= list1.get(i);
                ans += tmp2;
                tmp2 = 1;
            }
            else{
                tmp2 *= list1.get(i);
            }
        }

        if (tmp2 != 1){
            ans += tmp2;
        }

        // 마지막으로 1 더해주기
        ans += cnt;


        System.out.println(ans);




    }// end main



}