[백준 / 골드4] 1744 수 묶기 (Java)

문제 보기

사용한 것

• 최대 결과를 구하기 위한 그리디

풀이 방법

• 문제를 풀이할 수 있게 입력 받아 배열에 저장하고 정렬해준다.
• 원활한 풀이를 위해 r과 l을 사용한다. 각각 우측 인덱스, 좌측 인덱스이다.
• 우선 양수부터 계산하기 위해 r을 사용한다.
• arr의 r 번째 인덱스과 r - 1 번째 인덱스가 모두 1보다 크다면 곱하여 결과에 더해준다. 가장 큰 결과가 나오도록 가장 큰 두 수부터 곱해서 더해주는 것이다.
• 1보다 큰 모든 수가 끝나면 1들이 남는다. 1을 남긴 이유는 곱해봣자 똑같은 수가 나오기 때문에 1씩 더해주는 것이 더 큰 수를 만들 수 있기 때문이다.
• 남은 1들을 결과에 더해준다.
• 그렇다면 이제 남은 것은 음수들과 0이다.
• 음수 x 음수는 양수이다. 따라서 arr의 l 번째 인덱스와 l - 1 번째 인덱스를 곱해서 결과에 저장한다. 마찬가지로 가장 작은 두 수를 곱하는게 최대 결과이다.
• 마지막에 하나의 숫자가 남을 수 있다. 더해준 뒤 result를 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        long result = 0;
        int r = N - 1;
        while (r > 0 && arr[r - 1] > 1) {
            result += (long) arr[r] * arr[r - 1];
            r -= 2;
        }
        while (r >= 0 && arr[r] > 0) {
            result += arr[r];
            r--;
        }
        int l = 0;
        while (l < r) {
            result += (long) arr[l] * arr[l + 1];
            l += 2;
        }
        if (l == r) {
            result += arr[l];
        }

        System.out.println(result);
    }
}