기술 블로그

18310번 안테나 본문

알고리즘 문제/BOJ

18310번 안테나

parkit 2020. 2. 25. 18:57
728x90
반응형

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


# 복습 # 추천 # 필수 # 코딩 # 코테 # 구현 # 생각 # 이분 탐색 # 중앙값 # 정렬


Greedy 문제인줄 알았는데


이분 탐색으로 접근했더니 풀렸다.



이 문제는 이분 탐색으로 풀기에는 비효율적이다.


어느 분께서 


처음 회차 이후에는 무조건 앞부분만 보게 되는데 뒷쪽을 탐색하지 않아도 되나요? 


라고 질문을 해주셨는데, 


솔직히 확실하게 알지 못 하여 따로 질문을 통해 알아냈다.


결론은 내 코드가 비효율적이다.


정렬 후 [ {0 + (n - 1)} / 2 ]가 답인데, 내 코드에서는 처음 진행할 시에 Start = 0, End = n - 1 이므로,


mid가 정답과 정확히 일치하는 (n - 1) / 2이기 때문에 그대로 출력되는 것이었다.


질문해주신 분 덕분에 알 수 있었다.




비효율적인 코드

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
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<int> v;
 
int bt(int Start, int End)
{
    int Left = Start;
    int Right = End;
    int dist = INT32_MAX, ret = 0;
 
    while (Left < Right)
    {
        int mid = (Left + Right) / 2;
        int pivot = v[mid];
        int temp = 0;
 
        for (auto i : v) {
            temp += abs(pivot - i);
        }
 
        // temp가 더 작다면 계속 작게 해줘서 최소의 temp가 될 때까지 진행
        if (temp <= dist) {
            Right = mid - 1;
            ret = pivot;
            dist = temp;
        }
        // temp가 더 크게 나오면 Left를 증가시킨다(다른 경우들이 있는지 파악)
        else {
            Left = mid + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    scanf("%d"&n);
 
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d"&input);
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    printf("%d\n", bt(0, n - 1));
 
    return 0;
}
cs









효율적인 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<int> v;
 
int main()
{
    cin.tie(0);
    scanf("%d"&n);
 
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d"&input);
        v.push_back(input);
    }
 
    sort(v.begin(), v.end());
 
    printf("%d\n", v[(n - 1/ 2]);
 
    return 0;
}
cs







728x90
반응형

'알고리즘 문제 > BOJ' 카테고리의 다른 글

18430번 무기 공학  (0) 2020.02.27
3019번 테트리스  (0) 2020.02.26
2504번 괄호의 값  (0) 2020.01.22
2258번 정육점  (0) 2020.01.21
2812번 크게 만들기  (0) 2020.01.21