BOJ_1744 : 수 묶기

👉 문제링크

1744번: 수 묶기

---

---

🔸 문제 분석 🔸

• N개의 수로 이루어진 수열이 있다.
  • 두 수를 묶어서 곱셈 연산을 할 수 있고, 나머지는 합연산으로 계산한다.
  • 계산 결과의 최대값을 출력한다.

🔸 문제 풀이 🔸

• 곱셈 연산으로 최대값을 만들어야 하므로 그리디 알고리즘으로 풀이한다.
  • 수열을 정렬 후, 1보다 큰 수 중에서 크기가 큰 수를 우선으로 짝을 지어 곱셈 연산을 진행한다.
  • 수가 1 미만인 수들은 음수끼리 만나 양수가 되거나, 0과 합쳐져 음수가 지워지므로 짝을 짓는다.

🔸 코드 🔸

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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);

        int answer = 0;
        int right = N - 1;
        int left = 0;

        while (right > 0) {
            if (arr[right] > 1 && arr[right - 1] > 1) {
                answer += arr[right] * arr[right - 1];
            } else break;
            right -= 2;
        }

        while (left < right) {
            if (arr[left] < 1 && arr[left + 1] < 1) {
                answer += arr[left] * arr[left + 1];
            } else break;
            left += 2;
        }

        for (int i = left; i <= right; i++) {
            answer += arr[i];
        }

        bw.write(Integer.toString(answer));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• N개의 수를 배열 arr에 저장후 오름차순 정렬한다.
• 뒤쪽 인덱스부터 두 원소가 모두 1보다 크면, 짝을 지어 곱셈 연산 후 누적한다.
• 앞쪽 인덱스부터 두 원소가 모두 1보다 작으면, 짝을 지어 곱셈 연산 후 누적한다.
• 곱셈 연산에 포함되지 않은 나머지 부분인 left ~ right 인덱스의 값을 누적한다.
• 누적된 값을 출력한다.

---

🔸 end 🔸

• 문제에 제시된 예제 입력이 다양해서 바로 풀이할 수 있었다.
  • 처음엔 뒤쪽 인덱스만 확인했는데, 음수가 포함될 수 있다는걸 예제 입력 4번에서 알고 앞쪽 인덱스 확인 부분을 추가했다.