<링크>

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


<소스코드>

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
#include<stdio.h>
int main()
{
    int t[1000000];
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i)
        scanf("%d", t + i);
    int l = 0, r = 1000000000;
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        long long s = 0;
        for (int i = 0; i < N; ++i)
            if (t[i] > m)
                s += t[i] - m;
        if (s >= M)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d", ans);
}
cs


<풀이>

이분탐색으로 찍어본 높이 하나당 모든 나무를 살펴봐야하기 때문에

시간복잡도는 

이 된다.

만약 벌어들인 나무가 M이상이면 높이를 더 높여봐야하고, 그럴때마다 답이 갱신된다.

M보다 못벌었으면 높이를 더 낮춰야한다.

저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 13423 Three Dots  (0) 2018.08.02
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int serch(int);
vector<int> v;
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        v = vector<int>();
        int ans = 0;
        int N;
        scanf("%d", &N);
        for(int i=0;i<N;++i)
        {
            int tmp;
            scanf("%d", &tmp);
            v.push_back(tmp);
        }
        sort(v.begin(), v.end());
        for(int i=0;i<N-1;++i)
            for (int j = i + 1; j < N; ++j)
            {
                int d=v[j] - v[i];
                if (serch(v[j] + d))
                    ++ans;
            }
        printf("%d\n", ans);
    }
}
int serch(int target)
{
    int l = 0;
    int r = v.size() - 1;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (v[m] == target)
            return 1;
        
        if (v[m] > target)
            r = m - 1;
        else
            l = m + 1;
    }
    return 0;
}
cs


<풀이>

출제의도는 이분탐색인 것 같다. 두 점을 찍고, 나머지 한 점이 있는지 없는지 이분탐색으로 확인한다.

시간은 N^2*(logN)이 걸린다.

다른 풀이 방법도 있는데 


<소스코드>

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
#include<stdio.h>
#include<algorithm>
using namespace std;
int dot[1000];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N;
        scanf("%d", &N);
        for (int i = 0; i < N; ++i)
            scanf("%d", dot + i);
        sort(dot, dot + N);
        int ans = 0;
        for (int i = 1; i < N - 1; ++i)
        {
            int l = 0;
            int r = N - 1;
            while (l < r)
            {
                int ldis = dot[i] - dot[l];
                int rdis = dot[r] - dot[i];
                if (ldis == rdis)
                {
                    ++ans;
                    ++l;
                }
                else if (ldis < rdis)
                    --r;
                else
                    ++l;
            }
        }
 
        printf("%d\n", ans);
    }
}
cs


<풀이>

s++ e--를 이용하는 방법이다. 가운데 점을 찍고, 좌측끝과 우측끝에서부터 간격을 비교하며

좌간이 넓으면 좌++ , 우간이 넓으면 우-- 한다.

이렇게 하면 중앙점한번 찍을때마다 모든 노드를 확인하기 때문에 N^2으로 끝낼 수 있다. 

저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2018.08.30
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

<링크>

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


<소스코드>

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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
queue<int> q;
vector<pair<int, int>> adj[10001];
int s, d;
int bfs(int);
int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; ++i)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    scanf("%d%d", &s, &d);
    int ans = 0;
    int l = 1, r = 1000000000;
    int m;
    while (l <= r)
    {
        m = (l + r) / 2;
        int to = bfs(m);
        if (to) {
            if (ans < m)
                ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d", ans);
}
int bfs(int weight)
{
    int isVisited[10001] = { 0, };
    q = queue<int>();
    isVisited[s] = 1;
    q.push(s);
    
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        if (cur == d)
            return 1;
        int s = adj[cur].size();
        for (int i = 0; i < s; ++i)
        {
            int to = adj[cur][i].first;
            int cost = adj[cur][i].second;
            if (!isVisited[to] && cost >= weight)
            {
                isVisited[to] = 1;
                q.push(to);
            }
        }
    }
    return 0;
}
    
 
cs


<풀이>

이분탐색 + BFS문제이다.

A도시에서 B도시까지 넘겨줄 수 있는 최대중량을 이분탐색으로 찍는다.

이분탐색은 답을 찍어볼 때 굉장히 유용하다는 것을 다시 한번 느꼈다.


2018/07/22 - [알고리즘 풀이/이분탐색] - 백준 3079 입국심사 :: 들짐승


찍는 값의 범위는 1~1000000000 이다.

찍은 값으로 BFS를 돌린다. 

현재 노드와 인접해있고, 방문하지 않았으며, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 넘어갈 수 있으므로 큐에 넣어준다.

도착지가 발견되면 더이상 가지를 뻗을 필요가 없으므로 리턴한다.

이 때, 넘어가는 다리의 용량이 내가 찍은 값보다 같거나 크면 이라는 조건 때문에 도착지를 발견못하고 큐가 비어버렸을 때는

0을 리턴해주고,

도착지를 찾은 경우 1을 리턴한다.


● 0이 리턴된 경우 : 찍어봤던 중량을 더 줄여봐야하기 때문에 right=mid-1

● 1이 리턴된 경우 : 찍어봤던 중량이 가능하다는 뜻이므로 최적의 값을 찾기 위해 더 큰 중량으로 실행해본다. left=mid+1

이 때, 정답을 갱신한다.


<시간복잡도>

이분탐색시간 :

 


BFS시간 : 인접리스트로 구현했기 때문에


따라서 최대 3300,000 이 걸리기 때문에 1초 안에 가능하다.

 



저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2018.08.30
백준 13423 Three Dots  (0) 2018.08.02
백준 3079 입국심사 :: 들짐승  (0) 2018.07.22

<링크>

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


<풀이>

그냥 무작정 찍기로 총 걸린 시간을 찍는다. 이 때 이분탐색으로 찍는다.
최대시간은 제일 오래걸리는 심사대*인원수 이다. (초기 right 값)

l=1  
r=60 
mid  = 30 
tot = 30/7 + 30/10 = 7 //총 걸린시간으로 몇명이 지나갔는지 확인 ( 30분동안 최대 몇명이 지나갈수있는가 ) 
->몫만 있으면 됨 
이시간안으로는 총인원이 턱도없으면 
시간을 늘려줘야되고 

총인원보다 많은인원을 통과시킬수있으면 시간을 줄이고 
총인원보다 같더라도 시간을 줄여봐야한다. 왜냐하면 어느게이트에 갔냐에 따라서 시간이 더 줄어들수있기 때문 


right= 29 
left=1 
mid=15 
tot=15/7+15/10=3 //모자름 

r=29 
l=16 
m=22 
tot=22/7+22/10 = 5 //모자름 

r=29 
l=23 
m=26 
tot=26/7+26/10=5 //모자름 

r=29 
l=27 
m=28 
tot=28/7+28/10=6 //충분 

r=27 
l=27 
m=27 
tot=27/7+27/10=5 // 모자름 

●이분탐색 : 답을 찍어보는 경우에 사용된다
●이분탐색 다음 타겟 정하기 : 

최적의 해를 구하는 과정에서 
내가 구한값이 너무 작으면 더큰게 필요하니까 left=mid+1 해주고 
구한값이 너무 크면 더 작은게 필요하니까 right=mid-1 해주고 
구한값으로 만족하다면 ? (==일때는) -> 최적의해가 최소값이라면 right=mid-1 해서 더 줄여서 시도해본다. 
최적의 해가 최대값이라면 left=mid+1 해주면된다. 
어차피 이분탐색은 반복되더라도 l<=r일때까지만 하고 logN의 시간복잡도이기 때문에 끝까지 가봐도 시간이 충분하다.

저작자표시

'알고리즘 풀이 > 이분탐색' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2018.08.30
백준 13423 Three Dots  (0) 2018.08.02
백준 1939 중량제한 :: 들짐승  (0) 2018.07.23

+ Recent posts

티스토리툴바