How We Coding

[3124] 최소 스패닝 트리

PS/SW Expert Academy2018. 6. 20. 21:11

### SW Expert Academy - D4 ###


[3124] 최소 스패닝 트리 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct P { int f, t, w; };
 
int p[100001];
 
bool cmp(P a, P b)
{
    return a.w < b.w;
}
 
int find(int x)
{
    return p[x] = p[x] == x ? x : find(p[x]);
}
 
bool Union(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return 0;
    p[a] = b;
    return 1;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int v, e;
        scanf("%d%d", &v, &e);
 
        for(int i=1; i<=v; i++)
            p[i] = i;
 
        vector<P> g;
        for(int i=0; i<e; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            g.push_back((P){a, b, c});
        }
        
        sort(g.begin(), g.end(), cmp);
 
        long long ans=0LL;
        for(int i=0; i<e; i++) 
            if(Union(g[i].f, g[i].t)) 
                ans += g[i].w;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}
 
cs


>> Union-Find 를 이용한 크루스칼 알고리즘 사용.

>> ans 값은 int 범위를 벗어남에 주의.


'PS > SW Expert Academy' 카테고리의 다른 글

[1486] 장훈이의 높은 선반  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

[1486] 장훈이의 높은 선반

PS/SW Expert Academy2018. 6. 20. 21:09

### SW Expert Academy - D4 ###


[1486] 장훈이의 높은 선반 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw&categoryId=AV2b7Yf6ABcBBASw&categoryType=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
#include <stdio.h>
 
int h[21];
int n, b, ans;
 
void go(int idx, int sum)
{
    if(sum >= b) {
        if(ans > sum-b)
            ans = sum-b;
        return ;
    }
    if(idx == n) return ;
 
    go(idx+1, sum+h[idx]);
    go(idx+1, sum);
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        scanf("%d%d", &n, &b);
 
        ans = 0;
        for(int i=0; i<n; i++) {
            scanf("%d", h+i);
            ans += h[i];
        }
 
        go(0, 0);
        printf("#%d %d\n",  tc, ans);       
    }
    
    return 0;
}
 
cs


>> n 제한이 20이므로 2^20 = 1048576 이므로 모든 경우의 수를 다 확인해봐도 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[4408] 자기방으로 돌아가기  (0) 2018.06.10

[4408] 자기방으로 돌아가기

PS/SW Expert Academy2018. 6. 10. 00:57

### SW Expert Academy - D4 ###


[4408] 자기방으로 돌아가기 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8


<소스코드>


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
#include <stdio.h>
 
int main()
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
 
    for(int tc=1; tc<=T; tc++) {
        int n, ans=0;
        int room[201]={0};
        scanf("%d", &n);
 
        while(n--) {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a > b) { int t=a; a=b; b=t; }
            
            if(a&1) a++;
            a/=2; 
 
            if(b&1) b++;
            b/=2; 
 
            for(int i=a; i<=b; i++)
                room[i]++;
        }
        
        for(int i=1; i<=200; i++)
            if(ans < room[i])
                ans = room[i];
        printf("#%d %d\n", tc, ans);
    }
     
    return 0;
}
 
cs


- 1, 2번방의 복도 번호를 1로, 3, 4번방의 복도 번호는 2로 ... 이런식으로 값을 설정

- 같은 복도 번호를 동시에 갈 수 없기 때문에, 특정 복도 번호를 최대로 지나쳐야하는 경우가 답이 된다.

'PS > SW Expert Academy' 카테고리의 다른 글

[3124] 최소 스패닝 트리  (0) 2018.06.20
[1486] 장훈이의 높은 선반  (0) 2018.06.20

티스토리툴바