[백준 1744] 수 묶기 (JAVA)

백준 1744번 문제  - 수 묶기

1744번: 수 묶기

---

문제 분석

 

• 수열이 주어졌을 때, 순서와 상관없이 더하거나 곱해 최대 값을 알아내 출력해라
  • 곱하는 것은 한번 혹은 안하는 것만 가능하다

---

 

해결 키 포인트

 

• Arrays.sort() 사용
• 그리디 알고리즘 사용
• 양수와 음수 다르게 계산
  • 양수: 큰 수끼리 곱한다.
  • 음수: 작은 수끼리 곱한다.

---

그리디 알고리즘 (탐욕 알고리즘)

 

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

쉽게 말해, 지금의 최선 = 전체의 최선

 

뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 
서울에서 대구의 최솟 값을 선택하고, 대구에서 부산까지의 최솟값을 선택하는 알고리즘

파이썬 알고리즘 인터뷰 (나무위키)

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 수 입력
        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        // 정렬
        Arrays.sort(nums);

        // 최대 합
        int result = 0;

        int i = N - 1;

        // 양수 값일 경우 큰 수부터 확인
        while (i >= 0 && nums[i] > 0) {
            // i-1이 0보다 크거나 같을 때 , 두 수의 곱이 두수의 합보다 크면
            if (i - 1 >= 0 &&
                    nums[i] * nums[i - 1] > nums[i] + nums[i - 1]) {
                // 결과에 두수의 곱을 더하고, i 두개 넘어가기
                result += nums[i] * nums[i - 1];
                i -= 2;
            }
            // 두 수의 합이 더 크거나, i-1이 0보다 작으면
            else {
                // num[i]를 더하고 i 한개 넘어가기
                result += nums[i];
                i--;
            }
        }

        // 음수 값일 경우 작은 수부터 확인
        int lastIndex = i;
        i = 0;
        while (lastIndex >= i) {
            if (lastIndex >= i + 1) {
                // 결과에 두수의 곱을 더하고, i 두개 넘어가기
                result += nums[i] * nums[i + 1];
                i += 2;
            }
            // i-1이 0보다 작으면
            else {
                // num[i]를 더하고 i 한개 넘어가기
                result += nums[i];
                i++;
            }
        }

        System.out.println(result);
    }
}