BOJ 13433 기하 문제

BOJ 13433 기하 문제

[분류 : 브루트포스]

 

[풀이]

  [순열] 기본적으로 N!을 생각할 수 있다. 단순히 원을 차례대로 나열하는 방법의 수로 생각하면 되겠다. (C++에선 next_permutation 사용)

  [유효성 검사] 원의 반지름 r1, r2, r3에 대해 r1 > r2, r3 > r2인 경우에 순서가 r1, r2, r3란 배치라면 유효성을 검사할 필요가 있다. 바로 이전 원 옆에 붙히지 못할 경우가 있단 의미다.

  [거리 계산] 바로 옆에 붙힐 수 없다면 x축 어디에 놓을 수 있는지 생각하기 전에 먼저 유효성 실패했을 때를 생각해보면 된다. 유효성 실패는 곧 아래 수식일 경우를 말한다.

$$sqrt(x^2 + (r_{i} - r_{j})^2) \lt r_{i} + r_{j}$$

  결국 바로 이전 원이 아니라 보다 더 이전의 원의 옆이란 소리가 된다. 따라서 순서가 결정됐을 때 이전 원들과의 거리를 계산하여 가능한 x값이 가장 큰 값을 가져오면 현재 순열의 배치를 완료할 수 있게 된다. 여기서 첫 번째 원과 마지막 원의 x좌표 거리를 가져와서 순열 중 가장 작은 값을 가져오시면 되겠다.

 

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N = 8;
int main() {
    int r[MAX_N], N, i, j, a[MAX_N];
    double adj[MAX_N][MAX_N] = {}, x[MAX_N], ans = 1e15;
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &r[i]);
        for (j = 0; j < i; j++)
            adj[i][j] = adj[j][i] = 2. * sqrt((double)r[i] * r[j]);
        a[i] = i;
    }
    do {
        x[0] = 0;
        for (i = 1; i < N; i++) {
            x[i] = 0;
            for (j = 0; j < i; j++)
                x[i] = max(x[i], x[j] + adj[a[j]][a[i]]);
        }
        ans = min(ans, x[N - 1]);
    } while (next_permutation(a, a + N));
    printf("%.11lf", ans);
    return 0;
}