백준: 16207번 (직사각형) [JAVA]

문제 링크

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

16207번: 직사각형

풀이

전체적인 풀이 과정은 다음과 같다.

1. 막대 개수 N과 막대 길이들을 입력받아 배열(bars) 생성, dp용 배열(long 타입) 생성
2. 막대 길이가 저장된 배열 bars를 내림차순 정렬
3. 막대 길이의 맨 앞부터 막대가 4개 남을 때까지, 막대를 하나씩 제외 시켜가며 재귀 함수 기반 탐색 call
   
4. 결과 반환

 문제에서 요구하는 답은 결국 주어진 막대들에서 최대한 많이 큰 직사각형들을 찾아내어 그 넓이들의 합을 나타내는 것이다. 그렇기 때문에 계속해서 직사각형들을 찾아내어 이들을 더해야 하다보니, 이 문제의 해결 방향을 재귀 기반 탐색으로 잡았다. 결국 현재 주어진 막대들 중에서 만들 수 있는 가장 큰 직사각형의 경우 최대한 큰 길이의 막대들을 골라 만드는 것이다. 막대들을 내림차순으로 정렬한 다음, 현 상태에서 2개의 쌍으로 만들 수 있는 막대들(조건 상 하나의 막대에서 -1을 시키는 것도 가능)을 2번 고른 다음 이들을 가지고 직사각형을 만들면 된다.
 이를 바탕으로 재귀함수를 구현하는데, 넘어오는 파라미터는 주어진 bars 배열과 현재 탐색을 시작할 위치, 그리고 전체 개수를 나타내는 N으로 구성한다. 만약 현재 탐색할 위치에서 남은 막대의 길이가 4개 미만이면 더 이상의 탐색이 불가능하니 0을 반환한다. 그 다음에는 앞선 방식대로 막대들을 찾은 다음, 이들을 가지고 넓이를 계산하고 현 위치 다음부터 다시 탐색을 하도록 재귀 함수를 call하여 그 결과를 누적하면 된다.
 물론 추가로 단순히 이렇게 탐색을 하는 경우 경우의 수가 너무 많을 수 있어, dp를 적용하여 연산 결과를 재활용하도록 했다.

 

public class Main {
    static Long[] dp;//dp용 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Integer[] bars = new Integer[N];
        dp = new Long[N];
        Arrays.fill(dp, -1L);

        long answer = 0;

        for (int i = 0; i < N; i++) {
            bars[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(bars, Collections.reverseOrder());//막대 내림차순 정렬

        for (int i = 0; i < N - 3; i++) {//하나씩 제외시키며 탐색 적용
            answer = Math.max(answer, makeSquare(i, bars, N));
        }

        System.out.println(answer);
        return;
    }

    static long makeSquare(int startIndex, Integer[] bars, int N) {
        if (startIndex >= N - 3) {//현 상황에서 남은 막대 개수가 4개 미만
            return 0;
        }

        if (dp[startIndex] != -1L) {//dp값이 존재
            return dp[startIndex];
        }

        int sideA = 0, sideB = 0, sideAIndex = N, sideBIndex = N;

        for (int i = startIndex; i < N - 1; i++) {//막대길이 find
            if (bars[i].equals(bars[i + 1])  || bars[i].equals(bars[i + 1] + 1)) {
                sideA = bars[i + 1];
                sideAIndex = i + 1;
                break;
            }
        }

        for (int i = sideAIndex + 1; i < N - 1; i++) {//막대길이 find
            if (bars[i].equals(bars[i + 1])  || bars[i].equals(bars[i + 1] + 1)) {
                sideB = bars[i + 1];
                sideBIndex = i + 1;
                break;
            }
        }

        //dp배열에 넓이를 저장하며 다음 탐색 결과 call
        return dp[startIndex] = (long) sideA * sideB + makeSquare(sideBIndex + 1, bars, N);
    }
}

결과