백준 - 16207: 직사각형

문제링크

 

문제 설명

풀이 흐름

• 각 막대별로 최대 1번씩만 기계를 사용할 수 있다는 것에 주목했습니다. 이는 길이의 차가 2이상인 막대는 직사각형의 평행한 변으로 만들 수 없다는 뜻입니다.
• 주어진 막대의 길이들을 정렬한 이후에 최대값부터 순차적으로 탐색하면서 직사각형을 만들 수 있는 4개의 수를 찾았습니다.
  • 최대값부터 순차적으로 탐색하는 이유는 다음과 같습니다. (a, b, c, d인 실수가 있고, a >= b >= c >= d 라고 가정)
    • (a * b + c * d) - (a * d + b * c) = a * (b - d) - c * (b - d) = (a - c) * (b - d) >= 0
    • (a * b + c * d) - (a * c + b * d) = a * (b - c) - d * (b - c) = (a - d) * (b - c) >= 0
    • 따라서 (a * b) + (c * d)가 가장 큰 값이므로 {a, b}, {c, d}의 쌍으로 직사각형을 만들 때가 가장 넓이가 최대입니다.
  • 직사각형이 되기 위해선 마주보는 변의 길이가 같아야 됩니다. 그러므로 {a, a + (1 or 0), b, b + (1 or 0)}이 되는 조합을 찾아야 합니다. (tmp는 직사각형을 만들 막대의 길이, i는 tmp에 값을 넣을 인덱스라고 가정)
    • i가 양수라면 한 변의 길이를 정하기 전이라는 뜻이므로 현재 탐색 중인 값을 tmp[i]에 넣습니다.
    • i가 음수라면 현재 탐색 중인 값을 tmp[i - 1]과 비교합니다.
      • 만약 현재 탐색 중인 값이 tmp[i - 1]과 2 이상 차이나면 tmp[i - 1]에 현재 탐색 중인 값을 넣습니다.
      • 만약 현재 탐색 중인 값이 tmp[i - 1]과 1 이하로 차이나면 tmp[i]에 현재 탐색 중인 값을 넣고 i를 1 증가시킵니다.
      • 만약 i가 4가 되면 tmp에 있는 값들로 직사각형의 넓이를 구하고 ans에 더해준 뒤 i를 0으로 초기화 시키고 위 과정을 반복합니다.

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] arr = new long[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        long ans = 0;
        long[] tmp = new long[4];
        int idx = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (idx % 2 == 0) {
                tmp[idx] = arr[i];
                idx++;
            } else {
                if (tmp[idx - 1] - arr[i] <= 1) {
                    tmp[idx] = arr[i];
                    idx++;
                } else {
                    tmp[idx - 1] = arr[i];
                }
            }
            if (idx == 4) {
                ans += tmp[1] * tmp[3];
                idx = 0;
            }
        }

        bw.write(String.valueOf(ans));

        bw.flush();

        bw.close();
        br.close();
    }
}