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

github : https://github.com/junho0956/Algorithm/blob/master/2805/2805/%EC%86%8C%EC%8A%A4.cpp

 

설명은 코드에 있습니다.

** 가장 중요한 문제의 핵심은 적어도 M 미터를 가져갈 수 있는 절단기의 높이를 최대로 만들어 주는 것입니다.

** 그래야 최소한의 나무 손실을 막으면서 원하는 만큼 가져갈 수 있습니다.

 

더보기
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
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    long long M, len, cnt, height = 0;
    vector<long long> v;
    long long left = 0, right = INT_MAX;
 
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> len;
        v.push_back(len);
    }
 
    while (left <= right) {
        long long mid = (left + right) / 2;
        cnt = 0;
        for (int i = 0; i < N; i++) if (v[i] >= mid) cnt += v[i] - mid;
 
        // cnt 가 M 보다 작다는 것은 절단기의 높이가 크다는 것을 의미 => 절단기의 높이를 낮춰야함
        if (cnt < M) right = mid - 1;
        // cnt 가 M 보다 크다는 것은 절단기의 높이가 작다는 것을 의미 => 절단기의 높이를 높여야함d
        else if (cnt > M) {
            left = mid + 1;
            // 적어도 M 미터를 넘게 가져갈 수 있긴 하니 현재 절단기 높이가 height 보다 크다면 갱신
            height = height < mid ? mid : height;
        }
        // 현재 cnt 가 M 미터를 정확히 가져갈 수 있다면 최적의 해
        else {
            height = mid;
            break;
        }
    }
 
    cout << height;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10815번 숫자 카드  (0) 2020.01.16
BOJ 2110번 공유기 설치  (0) 2020.01.16
BOJ 1654번 랜선 자르기  (0) 2020.01.16
BOJ 1167번 트리의 지름  (0) 2020.01.15
BOJ 1967번 트리의 지름  (0) 2020.01.15

BOJ : https://www.acmicpc.net/problem/1654

GitHub : https://github.com/junho0956/Algorithm/blob/master/1654/1654/%EC%86%8C%EC%8A%A4.cpp

 

아 다시는 풀고싶지 않은 문제이다.

12번의 제출 끝에 정답을 맞춘 문제다.

막힐 때는 고집부리지 않고 게시판도 읽어보고 검색도 해보고 배우는 습관을 들여야겠다.

 

12번의 제출 끝에 알게된 결함은 int <-> long long 때문이였다.

타입 변환을 제외하고는 크게 문제될게 없는 문제이다.

 

더보기
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
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
vector<long long> v;
long long N, K, k_num, Max;
 
long long solve() {
    long long left = 0, right = INT_MAX;
    long long result = 0;
 
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long cnt = 0;
        for (long long i = 0; i < v.size(); i++) cnt += v[i] / mid;
 
        if (cnt >= N) {
            left = mid + 1;
            result = result < mid ? mid : result;
        }
        else right = mid - 1;
    }
 
    return result;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> K >> N;
    for (long long i = 0; i < K; i++) {
        cin >> k_num;
        v.push_back(k_num);
        Max = Max < k_num ? k_num : Max;
    }
 
    long long result = solve();
    cout << result;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2110번 공유기 설치  (0) 2020.01.16
BOJ 2805번 나무 자르기  (0) 2020.01.16
BOJ 1167번 트리의 지름  (0) 2020.01.15
BOJ 1967번 트리의 지름  (0) 2020.01.15
BOJ 11725번 트리의 부모 찾기  (0) 2020.01.14

BOJ : https://www.acmicpc.net/problem/1167

github : https://github.com/junho0956/Algorithm/blob/master/1167/1167/%EC%86%8C%EC%8A%A4.cpp

 

앞전에 설명한 BOJ 1967번 트리의 지름과 같은 유형이지만

케이스의 증가로 일반적인 방법으로 풀면 시간초과가 된다.

BOJ 1967번을 설명하면서 언급했듯이 트리의 지름이라는 것을 이해하는 것이 우선이다.

 

임의의 리프노드를 출발으로 최대값을 찾으면 최대값을 만드는데 최종 결정을 한 노드를 알게되고

이 노드가 트리의 지름을 이루는 2개의 노드 중 1개가 된다는 것이다.

그럼 이 노드를 이용해서 다시 1번만 dfs 를 돌면 트리의 지름을 구할 수 있게 된다.

 

더보기
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
#include <iostream>
#include <vector>
using namespace std;
 
bool visit[100001];
vector<pair<int, int> > v[100001];
int N, f, s, w;
int Max_node, Max_total;
 
void dfs(int now, int total) {
    if (visit[now]) return;
    visit[now] = 1;
 
    if (Max_total < total) {
        Max_total = total;
        Max_node = now;
    }
 
    for (int i = 0; i < v[now].size(); i++) {
        dfs(v[now][i].first, total + v[now][i].second);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> f;
        while (1) {
            cin >> s;
            if (s == -1) break;
            cin >> w;
            v[f].push_back({ s,w });
            v[s].push_back({ f,w });
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (v[i].size() == 2) {
            dfs(i, 0);
            for (int i = 1; i <= N; i++) visit[i] = 0;
            dfs(Max_node, 0);
            break;
        }
    }
    
    cout << Max_total;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2805번 나무 자르기  (0) 2020.01.16
BOJ 1654번 랜선 자르기  (0) 2020.01.16
BOJ 1967번 트리의 지름  (0) 2020.01.15
BOJ 11725번 트리의 부모 찾기  (0) 2020.01.14
BOJ 1991번 트리 순회  (0) 2020.01.14

BOJ : https://www.acmicpc.net/problem/1967

github : https://github.com/junho0956/Algorithm/blob/master/1967/1967/%EC%86%8C%EC%8A%A4.cpp

 

처음에는 트리의 지름이라는 것을 단순히 리프노드 사이끼리의 최장거리 로만 생각했다.

그래서 풀어낸 코드는 리프노드일 경우 다른 리프노드를 찾아가는 dfs 를 했고

채점결과를 보니 정답은 받았지만 시간이 다른정답자에 비해 길다는 것을 알았다.

솔직히 문제를 풀면서 시간이 오래걸릴 것 같기는 했다.

각 리프노드마다 전체를 다 방문해야되니 O(N^2) 의 시간이 필요해서이다.

근데 이걸 어떻게 시간을 줄일 수 있는 걸까 고민을 해보았는데

트리의 지름이라는 것을 이해하게 되니 더욱 쉬워졌다.

 

트리의 지름이라는게 결국 가장 긴 리프노드 사이의 값이 되고 지름을 위한 노드가 2개가 명확히 결정된다.

그럼 임의의 리프노드에서 처음에 탐색을 마치게 되면

임의의 리프노드가 지름을 이루는 노드 중 1개가 아니더라도

최장거리를 반환하기 위한 노드는 지름을 이루는 2개의 노드 중 1개가 된다는 것이다.

 

결국 1번의 탐색으로 지름 중 1개의 노드를 찾을 수 있게 되는 것이다.

그럼 이 노드를 이용해서 다시 한번 전체를 탐색해주면 나머지 찾지 못한 노드를 찾을 수 있게 되는 것이다.

이해가 안된다면 .. 다시 한번 읽어보자

 

BOJ 1167번 문제가 같은 트리의 지름인데 노드가 10배가 많으니 현재 코드로는 시간초과가 당연할 수 밖에 없다.

위에서 설명한 2번의 dfs 를 이용하는 코드는 BOJ 1167번을 풀면서 다시 한번 설명하겠다.

BOJ 1167번 : 트리의 지름 https://junho0956.tistory.com/122?category=825559

 

아래 코드는 단순히 1967 번을 푸는데 문제는 없으므로 단순 이해를 위해 도움이 되었으면 한다.

 

더보기
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool visit[10001];
vector<pair<int, int> > v[10001];
int N, f, s, w;
 
int dfs(int now) {
    if (visit[now]) return 0;
    visit[now] = 1;
 
    int total = 0;
    for (int i = 0; i < v[now].size(); i++) {
        if (visit[v[now][i].first] == 0) {
            total = max(total, dfs(v[now][i].first) + v[now][i].second);
        }
    }
 
    return total;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        cin >> f >> s >> w;
        v[f].push_back({ s,w });
        v[s].push_back({ f,w });
    }
 
    int Max = 0;
    for (int i = 1; i <= N; i++) {
        if (v[i].size() == 1) {
            int len = dfs(i);
            Max = Max < len ? len : Max;
            for (int i = 1; i <= N; i++) visit[i] = 0;
        }
    }
 
    cout << Max;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1654번 랜선 자르기  (0) 2020.01.16
BOJ 1167번 트리의 지름  (0) 2020.01.15
BOJ 11725번 트리의 부모 찾기  (0) 2020.01.14
BOJ 1991번 트리 순회  (0) 2020.01.14
BOJ 2146번 다리 만들기  (0) 2020.01.14

+ Recent posts

티스토리툴바