문제링크 : https://www.acmicpc.net/problem/2805


아이디어

  • 접근 1. 브루트포스로 일단 접근
    • 모든 높이에 대해, 모든 나무를 탐색하여 높이의 최대값을 구함
    • O(K * N) = O(1e9 * 1e6) > 시간초과
  • 접근 2. 높이를 이진탐색하여, 그떄마다 가져갈 수 있는 나무를 탐색
    • 이떄, 가능한것중에 가장 큰 값을 가져가야함

시간복잡도 계산

  • 높이를 이진탐색 : O(lgK)
    • 각 높이에서 모든 나무를 순회 : O(N)
    • 총합 : O(NlgK) = 1e6 * lge9 = 1e6 * 30 = 3e7 > 가능'

자료구조

  • 전체 나무 : int[]
    • 나무 최대 길이 : 2e9 > int 가능
  • 자르는 나무 높이 총합
    • 최대값 : 나무수 * 나무길이 최대 = 1e6 * 2e9 > long long 사용

코드(C++)

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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
int N,M;
 
bool chk(int num) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        // 나무 자르고 남은값
        int et = tree[i] - num;
        if(et > 0) rs += et;
    }
    
    if(rs >= M) return 1;
    return 0;
}
 
int binsearch(int st, int en) {
    if(st==en) return st;
    
    // 여기서 (st+en)/2 로 계산하게되면,
    // 가능한 것중 가장 낮은값을 찾게됨
    // 가능한 것중 가장 높은 값 찾기위해 (st+en)/2 로 사용
    int mid = (st+en+1)/2;
    if(chk(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    // 나무값 먼저 받아옴
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(0,1e9) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 케이스를 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18

문제링크 : https://www.acmicpc.net/problem/1939


아이디어

  • 접근 1. BFS로 두 섬을 잇는 경로 확인
    • 근데 BFS를 통해 최대값 구하기? > 불가능
  • 접근 2. 최소값이므로, 다익스트라?
    • 다익스트라는 간선의 가중치가 주어질떄 최소 거리를 구하는 문제
    • 이 문제는 연결할 수 있는 최대값을 구하는 문제이므로 불가능
  • 접근 3. 이진탐색으로 중량의 최대값을 구하기
    • 중량이 정해지면 BFS로 건널수 있는지 확인

시간복잡도 계산

  • 중량의 최대값 구하기 : lgC
    • BFS로 건널수 있는지 확인
      • BFS : O(V+E)
      • V : N
      • E : 2M (다리가 양방향이므로 2배)
      • O(V+E) = O(N + 2M) = O(N)
  • 총합 : O(lgC * N)
    • N : 1e5
    • lgC : 30
    • 총합 : 3e6 > 가능

자료구조

  • BFS 사용할 인접리스트 vector<pair<int, int>>
    • 거리는 최대 1e9이므로 INT 가능

코드(C++)

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 <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<pair<int, int>> adj[100010];
int st,en;
 
bool bfs(int num) {
    bool chk[100010];
    fill(chk, chk+100010, 0);
    
    queue<int> q;
    q.push(st);
    chk[st] = 1;
    
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        if(eq==en) return 1;
        
        for(auto x : adj[eq]) {
            int ec = x.first;
            int ei = x.second;
            
            if(ec < num) continue;
            if(chk[ei]) continue;
            
            chk[ei] = 1;
            q.push(ei);
        }
        
    }
    
    return 0;
    
}
int binsearch(int st, int en) {
    if(st==en) {
        return st;
    }
 
    // 여기서 내림을 하게되면, 가능한 수중 가장 낮은 값을 찾게됨
    // 그래서 올림을해줘야 가능한수 중 가장 높은값을 찾음
    int mid = (st+en+1)/2;
    if(bfs(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1) ;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    cin >> st >> en;
    
    cout << binsearch(1,1e9) << '\n';
    return 0;
}
 
 
cs

문제유형

  • 이진탐색 - 케이스를 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 8983 사냥꾼  (0) 2021.03.18
백준 2805 나무 자르기  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17

문제링크 : https://www.acmicpc.net/problem/1300


아이디어

  • 일단 브루트포스로, N*N 탐색 수행
    • 시간복잡도 : O(N^2) = 1e10 > 시간초과
      • 내가 어떤 수를 정했을때, 그 수보다 작거나 같은수의 개수를 구하는 방법
    • 최소 시간복잡도 : O(N)
    • A[j][i]에서, j만큼 나눠서 더하면 됨
      • 단, 이때 최대값은 N 초과하면 안됨
        • 그럼 숫자를 이진탐색하면서
        • k보다 그 숫자보다 작은 숫자가 크거나 같은 값을 구하면 됨

시간복잡도 계산

  • 작거나 같은 수 구하는 방법 : O(N)
    • 이진탐색 : lgN
    • 총합 : O(NlgN)

자료구조

  • 해당 수보다 작은 수 구할때
    • 최대값 : N * N = N^2 = 1e10 > long long 사용

코드(C++)

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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
int N,K;
 
ll cal(int num) {
    int rs=0;
    for(int i=1; i<=N; i++) {
        // 한 줄에 최대 N개까지 있음
        rs += min(N, num/i);
    }
    return rs;
}
 
int binsearch(int st, int en, int tar) {
    if(st== en) {
        return st;
    }
    
    int mid = (st+en)/2;
    if(cal(mid) < (ll)tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
}
 
int main() {
    cin >> N >> K;
    
    // 구하려는 값은 최대 K보다 클 수 없음
    cout << binsearch(1,K,K) << '\n';
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 케이스를 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17

+ Recent posts

티스토리툴바