[백준] 1744번 : 수 묶기 - 자바(Java)

Problem 🔒

문제

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

 

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

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

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

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

예제 입력 2

6
0
1
2
4
3
5

예제 출력 2

27

예제 입력 3

1
-1

예제 출력 3

-1

예제 입력 4

3
-1
0
1

예제 출력 4

1

예제 입력 5

2
1
1

예제 출력 5

2

 

---

Consider

1. 음수는 2개씩 곱하는 것이 더 큰 값을 만든다.
2. 홀수 개의 음수가 있을 경우 0이 있다면 곱하고, 0이 없다면 더한다.
3. 짝수와 0을 곱해선 안된다.
4. 홀수 개의 양수가 있을 경우, 제일 작은 양수는 더해준다.
5. 양수에 1은 곱하는 것보다 더하는 것이 더 큰 값을 만든다.

Approach ⭕

1. 입력 및 초기화
   • 입력 받은 수를 저장할 배열을 생성한다.
   • 음수, 양수, 0의 개수를 저장할 변수를 생성하고 카운팅한다.
   • 입력 받은 배열을 오름차순으로 정렬한다.
   • 음수와 양수를 별도로 처리해주기 위해 len 변수를 생성한다.
2. 음수 처리(그리디 알고리즘)
   • i == len-1
     • i가 len-1이 되는 경우는 음수가 홀수 개이고, 0이 없을 때만 가능하다.
     • 가장 큰 음수(마지막 음수) 하나만 남은 상황이므로 ans에 더해준다.
   • i < len
     • 음수는 2개씩 곱하는 것이 더 큰 값을 만드므로 곱한 값을 ans에 더해준다.
3. 양수 처리(그리디 알고리즘)
   • (i==len) && (pl%2==1)
     • 양수가 홀수 개일 때, 가장 작은 양수(첫 번째 양수)는 더해준다.
   • i ≥ len
     • 양수는 두 수의 곱과 합을 비교한 후 더 큰 값을 ans에 더해준다.
     • 위의 조건에서 양수가 짝수 개인 경우도 고려해준다.

---

Solution 💡

public class Main{
    static int N, nums[], ma=0, ze=0, pl=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nums = new int[N];
        for(int i=0; i<N; i++){
            nums[i] = sc.nextInt();
            if(nums[i]<0) ma++;
            else if(nums[i]==0) ze++;
            else pl++;
        }
        Arrays.sort(nums); // 오름차순 정렬
        int ans = 0;
        int len = ma+ze;
        int i=0;
        while(i<N){
            // 음수
            if(i==len-1){ans+=nums[i]; i++; continue;}
            if(i<len){
                ans += nums[i]*nums[i+1];
                i+=2;
                continue;
            }
            // 양수
            if(i==len && pl%2==1){ans+=nums[i]; i++; continue;}
            if(i>=len){
                ans += Math.max(nums[i]*nums[i+1], nums[i]+nums[i+1]);
                i+=2;
            }
        }
        System.out.println(ans);
    }
}