Disjoint_Set의 개념으로 길이 배열을 한가지 더 선언해주어서 절대 차이만큼만 

더해주면서 저장하면 되는 것이었다. 

find 와 init 과정에서 parent 배열과 길이를 저장할 배열을 따로 만들어주었다. 

find를 호출할때마다 해당 노드의 루트노드를 탐색하고 루트노드까지의 길이를 해당 인덱스의

길이 배열에 저장해주었다. 

(어렵게 생각하기보단 풀리지 않는다면 Disjoint_set의 과정을 완벽히 이해해보시길 바랍니다.)

그래도 이해가 가지않는다면 댓글과 쪽지를 주세요!

스티커 이미지

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

3780번: 네트워크 연결
문제 종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다. 어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다. 클러스터 B를 제공하는 기업 J를 고른다.
www.acmicpc.net

<CODE>


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
//pda_pro12
#include<iostream>
#include<algorithm>
 
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define N_ 20001
#define mod (int)1e3
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pll;
typedef double db;
 
int n, m, t, par[N_], len[N_];
 
void init() {
    for (int i = 1; i <= n; i++)
        par[i] = i, len[i] = 0;
    return;
}
 
int find(int x) {
    if (x == par[x])
        return x;
    else {
        int tmp = find(par[x]); 
        len[x] += len[par[x]]; 
        par[x] = tmp; 
        return tmp;
    }
}
 
void Merge(int x, int y) {
    len[x] = abs(x - y) % mod; 
    par[x] = y; 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> t;
    while (t--) {
        cin >> n;
        init(); 
        char inp; int a, b;
        while (1) {
            cin >> inp;
            if (inp == 'O')
                break; 
            else if (inp == 'E') {
                cin >> a;
                find(a); 
                cout << len[a] << '\n';
            }
            else if (inp == 'I') {
                cin >> a >> b;
                Merge(a, b);
            }
        }
    }
    return 0;
}


저작자표시

'PS) BOJ > Disjoint_set' 카테고리의 다른 글

[C++]미로 만들기 [BOJ 2665]  (0) 2018.08.21
[C++] 공항 [BOJ 10775]  (0) 2018.08.17


굉장히 간단한 문제를 조건하나를 빠트려서 계속 헛다리 짚은 문제이다...
( 내시간... )

n번 게이트에 도킹 되면 가장 인접하면서 낮은 번호의 게이트로 도킹이 되고, 연결해야할 게이트가 
0번 밖에 남지 않았다고 한다면 마쳐주면된다. 

도킹 게이트가 0임을 포착한 순간 바로 입력하던 반복문도 빠져나오고 현 게이트 수를 출력하고 종료시켜줘야한다. 
(이거때매 30분넘게 해맸다...)

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

<CODE>


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
//pda_pro12
#include<iostream>
#define N_ 100001
 
using namespace std;
 
int g, p, par[N_], inp, cnt;
 
void init() {
    for (int i = 1; i <= g; i++)
        par[i] = i;
    return;
}
 
int find(int x) {
    if (x == par[x])
        return x;
    return par[x] = find(par[x]);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> g >> p;
    init();
    for (int i = 1; i <= p; i++) {
        cin >> inp;
        if (find(inp) == 0) {
            break;
        }
        if (find(inp)) {  // 내가 도킹하려는 곳이 가능한지 확인 
            cnt++;
            par[find(inp)] = find(find(inp) - 1);
        }
    }
    cout << cnt << '\n';
    return 0;
}


저작자표시

'PS) BOJ > Disjoint_set' 카테고리의 다른 글

[C++]미로 만들기 [BOJ 2665]  (0) 2018.08.21
[C++] 네트워크 연결 [백준 3780]  (0) 2018.08.17

올 초에 이분탐색 개념을 처음 알았을때 어떻게 이분탐색을 꾸역꾸역 끼워넣을지 고민했던 기억이...

생각해보면 무척 간단한거였다. 

문제 해결과정

1. 랜선의 길이의 상한과 하한을 잡아준다. 

2. 랜선의 하한과 상한을 기준으로 중간값을 구해주고 중간값을 길이로 가정하고 몇개의 랜선으로 쪼개  
   질수 있는지 탐색해본다.

<직접 손으로 써서 설명해봤는데 이해가 잘될지 모르겠다>

이렇게 탐색하면 1~최대 2147483647이니깐  NLogK만 끝낼수 있다 
(가정된 길이에 대한 갯수 구하는과정)N*LogK

(상한 하한의 길이만큼을 /2해가면서 탐색하므로 Log길이 만큼이된다.)

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


<Code>

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
//pda_pro12
#include<algorithm>
#include<iostream>
#define N_ 10001
#define INT 0x7fff0000
using namespace std;
 
typedef long long ll; 
int k, n, a[N_], Max;    ll lft, rgt; 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL); 
 
    cin >> k >> n; 
    for (int i = 0; i < k; i++) 
        cin >> a[i], Max = max(a[i],Max);             // 보유중인 랜선에 대한 정보를 입력받음 
    int ans = 0; 
    lft = 1;  rgt = Max; 
    while (lft <= rgt) {
        ll mid = (lft + rgt) >> 1; 
        int Sum = 0; 
        for (int i = 0; i < k; i++) 
            Sum += (a[i] / mid); 
        if (Sum >= n) 
            ans = mid,lft = mid + 1;
        else
            rgt = mid - 1; 
    }
    cout << ans; 
    return 0; 
}


저작자표시

'PS) BOJ > Binary Search' 카테고리의 다른 글

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16
[C++]입국심사[백준 3079]  (0) 2018.08.15

+ Recent posts

티스토리툴바