백준 1744 수 묶기(JAVA)

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

1744번: 수 묶기

 

알고리즘 분류: 그리디 알고리즘, 정렬

 

문제 풀이

먼저 이 문제를 보자마자 생각난 문제가 있었는데, 백준 1461 문제와 비슷하다 생각했다.

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

1461번: 도서관

왜냐하면, 이 문제에서 양수와 음수가 존재하고, 수를 묶었을 때 최대로 낼 수 있는 값을 찾아야 하기에,

양수는 양수끼리, 음수는 음수끼리 계산하는 것이 가장 큰 수일 것이라는 결론을 내렸기 때문이다.

그래서 처음엔 양수 리스트, 음수 리스트로 나누어 수를 저장한 뒤, 양수는 내림차순, 음수는 오름차순으로 정렬하여

상위 2개를 곱하고, 결과에 더하고, 2개를 못 빼면 그냥 더하고 루프 종료.

이렇게 알고리즘을 생각했었다.

 int index = 0;
        while (index<list.size()){
            if(index + 1 < list.size()){
                sum += (list.get(index) * list.get(index + 1));
                index +=2;
            }
            else{
                sum += list.get(index);
                break;
            }
        }

하지만, 틀렸다.

여기서 놓친것이 하나 있었는데, 2개를 뽑았을 때, 하나라도 1이라면, 곱하는 것보다는 더하는 것이

더 크다는 것을 놓쳤었다.

그래서 다시 수정하여

while (index < list.size()) {
            if (index + 1 < list.size() && list.get(index) != 1 && list.get(index + 1) != 1) {
                sum += (list.get(index) * list.get(index + 1));
                index += 2;
            }
            else {
                sum += list.get(index);
                index++;
            }
        }

이렇게 짜게 되었다.

 

그리고 1을 체크하는 부분은 음수에서는 할 필요가 없다.

음수는 무조건 곱하는 것이 이득이기 때문이다.

 

전체 코드

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


public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        List<Integer> reverselist = new ArrayList<>();

        for(int i = 0;i<n;i++){
            int k = Integer.parseInt(br.readLine());
            if(k<=0) reverselist.add(k);
            else list.add(k);
        }

        Collections.sort(list, Collections.reverseOrder());
        Collections.sort(reverselist);

        int sum = 0;

        int index = 0;
        while (index < list.size()) {
            if (index + 1 < list.size() && list.get(index) != 1 && list.get(index + 1) != 1) {
                sum += (list.get(index) * list.get(index + 1));
                index += 2;
            }
            else {
                sum += list.get(index);
                index++;
            }
        }
        index = 0;
        while (index < reverselist.size()){
            if(index + 1 < reverselist.size()){
                sum+= (reverselist.get(index) * reverselist.get(index + 1));
                index +=2;
            }
            else{
                sum+=reverselist.get(index);
                break;
            }
        }
        System.out.println(sum);
    }
}