[백준] 1744번 수 묶기 문제 (어떻게 묶으면 최대가 될까?) : Programming Story

1. 문제

www.acmicpc.net/problem/1744

문제는 위의 링크에 들어가면 확인할 수 있다.

2. 풀이

이 문제는 두 수를 잘 묶으면 곱하기가 된다는 문제를 바탕으로 어떻게 두 수를 곱할 때 최대가 될지 생각해보아야 하는 문제이다.

양수: 양수끼리는 서로 큰 숫자끼리 곱하면 최대가 된다. 1이랑 곱하는 것은 그대로 유지됨으로 1과 곱하기는 지양하는 것이 최대를 만들 수 있는 길이다.
음수: 음수는 작은 수끼리 곱하면 오히려 최대가 된다. 따라서 양수는 내림차순 정렬하고, 음수는 오름차순 정렬한 뒤에 둘 씩 곱해보는 것이 필요하다는 것을 알 수 있다.
만약 음수의 개수가 홀수이고, 0이 1개 이상 있다면 남는 음수 하나는 0과 곱해서 0을 만드는 것이 최대를 만들 수 있는 방법이다.
1은 양수지만 곱하기보다는 그대로 더하는 것이 최대를 만드는 방법이다. 1*1은 1이지만 1+1은 2이기 때문이다. 더하기를 하는 것이 나은 수이다.

이것을 바탕으로 문제에서 양수, 음수를 입력받아서 서로 다른 ArrayList에 구분해서 넣어준다. 1의 경우에는 양수지만 우리가 곱하지 않을 것이기 때문에 plus ArrayList에 넣어주지는 않는다.

3. 코드

이것을 코드로 구현한 것은 아래와 같다.

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ArrayList<Integer> plus=new ArrayList<>();
        ArrayList<Integer> minus=new ArrayList<>();
        int zerocount=0;
        int onecount=0;
        for(int i=0; i<n; i++){
            int x=sc.nextInt();
            if (x==1) onecount++; //1인 것은 안묶어야 최대
            else if (x>0) plus.add(x);
            else if (x<0) minus.add(x);
            else{
                zerocount++;
            }
        }
        Collections.sort(plus);  
        Collections.reverse(plus); //양수는 내림차순으로 정렬
        Collections.sort(minus); //음수는 오름차순으로 해야 곱했을 때 최대
        
        if (plus.size()%2==1){
            //양수가 홀수이면 하나는 1을 넣어준다
            plus.add(1);
        }
        if (minus.size()%2==1){
            if (zerocount>0){
                minus.add(0);
            }else{
                minus.add(1);
            }
        }
        int ans=onecount;
        for (int i=0; i<plus.size(); i+=2) {
            ans += plus.get(i) * plus.get(i+1);
        }
        for (int i=0; i<minus.size(); i+=2) {
            ans += minus.get(i) * minus.get(i+1);
        }
        System.out.println(ans);
    }
}

zerocount은 0의 개수, onecount는 1의 개수를 의미한다. 어짜피 둘 씩 곱해줄 것이기 때문에 양수의 개수가 홀수이면 그냥 1을 넣어주었다. 어짜피 1과 곱한 값은 하나를 더한 것과 동일하기 때문에 문제의 정답에 영향을 미치지 않기 때문이다. 나중에 둘씩 곱해주기 위해서 양수, 음수의 개수를 모두 짝수개로 맞추어주려고 한 것이다. 음수의 경우에는 개수가 홀수일 경우 그리고 0이 한개 이상 있을 경우 0과 곱해주면 되고, 아닌 경우 그냥 그 수 자체를 더해주면 되니 1을 추가해준 것이다.