[PS] BOJ1744 수묶기 ( Greedy ) with JAVA

1744번: 수 묶기

 

 

◎ 문제풀이

 

수열의 수는 음수 , 0, 양수가 가능하고 두개의 수를 묶어 곱한 뒤 합하는게 가능하다.  이때의 최대값을 구하는 문제이다. 합이 최대가 나오려면 음수와 양수는 분리되어야 한다. 음수와 양수의 곱은 음수가 나오기 때문이다.

 

- 음수인 경우

1) 절대값이 큰값끼리 곱해야 한다.

2) 곱할 음수가 없는 음수는 0과 곱하여 상쇄되어야 한다.

3) 0도 없으면 그대로 음수를 합해야 한다.

 

- 양수인 경우

1) 절대값이 큰값끼리 곱해야 한다. 

2) 1은 곱셈보다 더하기가 이득이다.

 

위 문제는 조건을 코드로 구현할 수 있는지 여부를 물어보는 문제이다.  

 

---

 

1) 절대값이 큰값끼리 곱해야 한다. 

음수와 양수의 자료구조를 분리하고 정렬을 하면 된다. 양수는 내림차순으로 음수는 오름차순으로 정렬한다. 

 

2) 연산은 곱하는 경우와 더하는 경우로 나뉜다. 

 

- 양수에서 곱하는 경우

두 개의 수가 있어야 한다. 그러나 1이 포함되면 안된다. 1이 포함되면 곱하기가 손해이다. 1이 포함되면 더하기가 이득이다. 

 

- 양수에서 더하는 경우

한 개의 수만 있거나 두 개의 수에 1이 포함된 경우에 더한다.

 

- 음수에서 곱하는 경우

두 개의 수만 있다면 무조건 곱하는 것이 이득이다. -1도 양수로 바꿀 수 있고 0도 곱하면 상쇄되니 이득이다.

 

- 음수에서 더하는 경우

수가 하나 밖에 없다면 어쩔 수 없이 더해야 한다. 

 

이렇듯 계산을 하려면 정렬된 자료구조에서 두 개의 수를 반복하여 가져와야 한다. 단순for문은 인덱스로 하나의 수에 접근할 때 유용하다. while문은 인덱스를 반복에서 분리할 수 있어 두개의 수에 유연하게 접근할 수 있다.

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

//BOJ1744 수묶기
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();

        for(int i=0;i<n;i++){
            int value = Integer.parseInt(br.readLine());
            if(value > 0) positives.add(value);
            else negatives.add(value);
        }

        Collections.sort(positives,Collections.reverseOrder()); //양수 내림차순
        Collections.sort(negatives); //음수 오름차순

        int ans = 0;
        
        // 양수인 경우 
        int i =0;
        while(i < positives.size()){
            // 곱하기 연산의 조건
            if( i+1 < positives.size() && positives.get(i) !=1 && positives.get(i+1) != 1){
                ans += positives.get(i++)*positives.get(i++);
            }
            // 더하기 연산의 조건
            else{ 
                ans += positives.get(i++);
            }
        }

        // 음수인 경우
        i =0;
        while(i < negatives.size()){
            //곱하기 연산의 조건
            if(i+1< negatives.size()) ans += negatives.get(i++)*negatives.get(i++);
            
            // 더하기 연산의 조건
            else ans += negatives.get(i++); 
        }

        System.out.println(ans);
    }
}