[백준 #1139] 울타리 - JAVA [자바], python[파이썬]

 

 

분류

비트마스킹, 다이나믹 프로그래밍, 비트필드를 이용한 다이나믹 프로그래밍

 

문제 설명

넓은 초원이 있다. 민식이는 초원에 심은 풀이 이상한 사람들이 밟을 까봐 걱정한다. 따라서, 민식이는 초원에 삼각형 모양의 울타리를 치려고 한다.

민식이는 지하실에 N개의 울타리가 있다. 민식이는 3개의 울타리를 이용해서 삼각형 모양을 만든다. 삼각형의 각 변은 울타리 하나이다. 울타리는 붙이거나 쪼갤 수 없다.

민식이는 삼각형 넓이의 합을 최대로 하려고 한다.

 

입력

첫째 줄에 울타리의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄에 각 울타리의 길이가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 줄을 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

 

예제 입력

7
3 4 5 6 7 8 9

4
1 2 4 8

4
7 4 4 4

16
21 72 15 55 16 44 54 63 69 35 75 69 76 70 50 81

 

 

예제 출력

36.754383146489694

0.0

6.928203230275509

7512.322360676162

 

힌트

 

코드 - 울타리.java

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

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

        int N = Integer.parseInt(br.readLine());
        String[] fenceStr = br.readLine().split(" ");
        int[] fences = new int[N];

        for (int i = 0; i < N; i++) {
            fences[i] = Integer.parseInt(fenceStr[i]);
        }

        Arrays.sort(fences);

        double[][] dp = new double[N][1 << N];

        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }

        System.out.printf("%.10f\n", solve(0, 0, fences, dp));
    }

    private static double solve(int idx, int bitmask, int[] fences, double[][] dp) {
        if (idx == fences.length) {
            return 0;
        }

        if (dp[idx][bitmask] != -1) {
            return dp[idx][bitmask];
        }

        double maxArea = solve(idx + 1, bitmask, fences, dp);

        for (int i = 0; i < fences.length; i++) {
            for (int j = i + 1; j < fences.length; j++) {
                for (int k = j + 1; k < fences.length; k++) {
                    if ((bitmask & (1 << i)) == 0 && (bitmask & (1 << j)) == 0 && (bitmask & (1 << k)) == 0) {
                        if (fences[i] + fences[j] > fences[k]) {
                            double area = getTriangleArea(fences[i], fences[j], fences[k]);
                            int newBitmask = bitmask | (1 << i) | (1 << j) | (1 << k);
                            maxArea = Math.max(maxArea, area + solve(idx + 1, newBitmask, fences, dp));
                        }
                    }
                }
            }
        }

        return dp[idx][bitmask] = maxArea;
    }

    private static double getTriangleArea(int a, int b, int c) {
        double p = (a + b + c) / 2.0;
        return Math.sqrt(p * (p - a) * (p - b) * (p - c));
    }
}

 

코드 분석하기

위의 코드는 주어진 울타리의 길이들을 이용하여 만들 수 있는 삼각형들의 넓이의 합을 최대로 하는 문제를 해결합니다. 이를 위해 비트마스킹, 다이나믹 프로그래밍, 그리고 비트 필드를 이용한 다이나믹 프로그래밍 기법을 사용합니다.

1. 입력을 받아서 처리합니다.
   • 첫 번째 줄에서 울타리의 개수 N을 입력받습니다.
   • 두 번째 줄에서 각 울타리의 길이를 입력받아 정수 배열에 저장합니다.
   • 울타리 길이 배열을 오름차순으로 정렬합니다.
2. 다이나믹 프로그래밍을 위한 2차원 배열 **dp**를 초기화하고, -1로 채웁니다.
3. solve 함수를 호출하여 결과를 출력합니다. 이 함수는 다음과 같은 인자를 받습니다.
   • idx: 현재 처리할 울타리의 인덱스
   • bitmask: 현재까지 사용한 울타리들을 나타내는 비트마스크
   • fences: 울타리 길이 배열
   • dp: 다이나믹 프로그래밍을 위한 배열
4. solve 함수는 다음 로직을 수행합니다.
   • 기저 사례: 모든 울타리를 처리했을 경우, 0을 반환합니다.
   • dp 배열에 이미 계산된 값이 있다면, 해당 값을 반환합니다.
   • 현재 울타리를 사용하지 않는 경우의 값을 계산하고, maxArea에 저장합니다.
   • 3중 반복문을 사용하여 가능한 모든 삼각형 조합을 확인합니다.
     • 해당 조합의 울타리들이 이미 사용되지 않았고, 삼각형을 만들 수 있는 경우에만 진행합니다.
     • 해당 조합으로 만들어진 삼각형의 넓이를 계산하고, 새로운 비트마스크를 생성합니다.
     • maxArea를 현재 조합의 넓이와 다음 인덱스의 값을 더한 것과 비교하여 최대값을 업데이트합니다.
5. getTriangleArea 함수는 세 변의 길이를 이용하여 삼각형의 넓이를 계산합니다. 이 함수는 헤론의 공식을 사용하여 삼각형의 넓이를 구합니다.

결과적으로, 위의 코드는 주어진 입력에 대해 만들 수 있는 삼각형들의 최대 넓이의 합을 계산하여 출력합니다.

코드 - 울타리.py

from math import sqrt
from itertools import combinations

def main():
    N = int(input())
    fences = list(map(int, input().split()))
    fences.sort()

    dp = [-1 for _ in range(1 << N)]

    def solve(state):
        if dp[state] != -1:
            return dp[state]

        dp[state] = 0

        for i, j, k in combinations(range(N), 3):
            if not (state >> i) & 1 and not (state >> j) & 1 and not (state >> k) & 1:
                if fences[i] + fences[j] > fences[k]:
                    p = (fences[i] + fences[j] + fences[k]) / 2
                    area = sqrt(p * (p - fences[i]) * (p - fences[j]) * (p - fences[k]))
                    dp[state] = max(dp[state], area + solve(state | (1 << i) | (1 << j) | (1 << k)))

        return dp[state]

    print(solve(0))

if __name__ == '__main__':
    main()

코드 분석하기

위의 코드는 주어진 울타리들의 길이를 사용하여 가능한 모든 삼각형의 넓이의 합을 최대로 하는 문제를 해결하는 코드입니다. 코드는 다음과 같은 방식으로 작동합니다.

1. 입력을 받아서 울타리의 개수 N과 울타리의 길이 리스트를 생성합니다. 그리고 울타리 리스트를 정렬합니다.
2. 다이나믹 프로그래밍을 위한 dp 배열을 초기화합니다. **dp**의 인덱스는 각 울타리의 사용 여부를 나타내는 비트마스크입니다.
3. solve 함수를 정의합니다. 이 함수는 현재 비트마스크 상태를 인자로 받아, 아직 사용하지 않은 울타리들을 이용하여 만들 수 있는 삼각형의 넓이의 최대 합을 반환합니다.
   • 만약 **dp**에 이미 계산된 값이 있다면, 그 값을 반환합니다.
   • 울타리 인덱스의 조합을 확인하고, 각 조합에 대해 다음을 수행합니다.
     • 현재 상태에서 해당 조합의 울타리들이 사용되지 않았고, 삼각형 조건을 만족한다면 (두 변의 합이 다른 변보다 크다면),
     • 해당 조합으로 삼각형을 만들고 넓이를 계산합니다.
     • 현재 상태에서 해당 조합의 울타리들을 사용한 상태로 넘어가고, 그에 대한 결과값을 가져옵니다.
     • 최대 넓이를 업데이트합니다.
   • 계산된 최대 넓이를 **dp**에 저장하고 반환합니다.
4. 초기 상태 (아무 울타리도 사용하지 않은 상태)에서 solve 함수를 호출하고 결과를 출력합니다.

위의 코드는 다이나믹 프로그래밍과 비트마스킹을 사용하여 효율적으로 문제를 해결하고 있습니다.

 

 

백준에서 문제 풀어보기

 

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

1139번: 울타리