반응형

문제 출처 :


https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD



알고리즘 분석 :


문제 해결에 필요한 사항

1. 이분탐색


이분탐색을 이용하여 균형점을 찾아 낼 수 있다. 


각 점 사이에 균형점이 있다 가정하고 이분탐색을 통해 


균형점을 찾아 인력을 계산해주어 답을 찾아낸다.






소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
 
typedef double db;
db pos[12];
db weight[12];
 
int main() {
    int tCase;
    scanf("%d"&tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        int n;
        scanf("%d"&n);
        db s = 0, e = 0.0;
        for (int i = 0; i < n; i++)
            scanf("%lf"&pos[i]);
        for (int i = 0; i < n; i++)
            scanf("%lf"&weight[i]);
 
        printf("#%d ", tc);
 
        for (int i = 0; i < n; i++) {
            s = pos[i], e = pos[i + 1];
 
            bool chk = false;
            db mid = (s + e) / 2;
            while (s <= e) {
                db mid = (s + e) / 2;
 
                db left = 0.0, right = 0.0;
                for (int i = 0; i < n; i++) {
                    db d = mid - (db)pos[i];
                    db m = weight[i];
                    if ((db)pos[i] < mid)
                        left += (m / (d * d));
                    
                    else if ((db)pos[i] > mid)
                        right += (m / (d * d));
                }
 
                if (left > right) {
                    s = mid + 0.000000000001;
                    if (s > e) {
                        printf("%.10lf ", mid);
                        chk = true;
                        break;
                    }
                }
                else if (left < right)
                {
                    e = mid - 0.000000000001;
                    if (s > e) {
                        printf("%.10lf ", mid);
                        chk = true;
                        break;
                    }
                }
                else {
                    printf("%.10lf ", mid);
                    chk = true;
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}
 
cs

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1251번] 하나로  (0) 2019.08.05
[4803번] 트리  (4) 2019.08.03
[1258번] 행렬찾기  (0) 2019.07.30
[1264번] 이미지 유사도 검사  (2) 2019.07.17
[1351번] 무한 수열  (0) 2019.07.14