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


으악..한 10번 틀렸네요...

문제를 잘읽읍시다..!



블록친 부분을 굉장히! 아주 잘 읽으셔야합니다.


저는 저 부분을 안읽고.. 내가 내려갈떄 내리막길이면 올라올떈 오르막길이니 어느방향에서 접근하냐에 따라 달라질 것이라고 생각했습니다.


삐삐!!!!!!!!

아니였습니다.


이 문제는 그냥 연결해라!!!!!!!!!!!!! 이 문제였습니다...

네!

MST.. 최소 스패닝 트리로 해결하는 문제입니다.


저는 크루스칼로 해결했습니다.


MST에는 크루스칼과 프림이 있는데 MST를 잘모르시는 분들은

공부를 하고 문제를 해결하시기 바랍니당!


간단하게 설명해드리자면! 싸이클이 생기지 않고 정점 n개를 간선 n - 1개로 연결하는 방법입니당!


크루스칼에서는 disjoint-set 알고리즘이 사용됩니당!

성능을 위해서는 우선순위-큐를 사용하시면 더 도움이 됩니다.!


이 문제는 input에서 오르막길이 0으로, 내리막길이 1로 들어오니 조심하셔서 푸십시용!


아래는 코드입니다.

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 10000
#define MAX_SIZE 1001
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int parent[MAX_SIZE];
int n, m;
vector<pair<pii, int> > edge;
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[x] = y;
        return 1;
    }
 
    return 0;
}
 
int f(int mul) {
    priority_queue<pair<int, pii> > pq;
 
    for (int i = 0; i <= n; i++) parent[i] = i;
 
    for (int i = 0; i < edge.size(); i++) pq.push(mp(!edge[i].second * mul, mp(edge[i].first.first, edge[i].first.second)));
 
    int ret = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt <= n - 1) {
        int k = pq.top().first * mul;
        int from = pq.top().second.first;
        int to = pq.top().second.second;
        pq.pop();
 
        bool tmp = merge(from, to);
        if (tmp) {
            cnt++;
            ret += k;
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m + 1; i++) {
        int a, b;
        bool c;
        cin >> a >> b >> c;
 
        edge.push_back(mp(mp(a, b), c));
    }
 
    int best = f(-1);
    int worst = f(1);
 
    cout << worst*worst - best*best;
 
    return 0;
}
 
cs


저작자표시

'알고리즘 > 최소 스패닝 트리(MST)' 카테고리의 다른 글

[1647] 도시 분할 계획  (0) 2017.08.30

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


처음에 그리디로 접근했는데.. 생각해보니 잘못된 접근이었습니다.

1, 10, 25, 100, 1000, 2500, ... 이렇게 코인이 진행되는데

이 수들이 서로 배수라면 그리디로 해결해도 괜찮지만

10에서 25, 1000에서 2500 ...... 이런식으로 배수가 아닌 경우가 존재합니다.


그렇기 떄문에 그리디는 잘못된 방법입니다.


다음에 생각한 방법이 재귀를 이용하여 완전탐색으로 해봤습니다.

결과는 잘나오나 어떤 부분이 틀린지 잘모르겠습니다.


그래서 블로그를 찾다 보니 푸는 방법이 굉장히 신기했습니다.


1, 10, 25

100, 1000, 2500

10000, 100000, 250000

.

.

.

한단계 단계가 100으로 나눌 떄 같아지는 것을 이용한 풀이입니다.


dp를 이용해서

0~99까지 최소 코인 수를 구합니다.


그 후에 입력 받은 n을 100씩 나누면서 더해주면 답이 되는 문제입니다..

어떻게 생각하지 ..ㅡ.ㅡ..... 천재들...


아래는 풀 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 1000000
#define MAX_SIZE 101
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int main() {
    int coin[] = { 1, 10, 25 };
    int dp[100] = { 0, };
 
    for (int i = 1; i < 100; i++) {
        dp[i] = INF;
        for (int j = 0; j < 3; j++) {
            if (i - coin[j] >= 0) {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }
 
    int t;
    cin >> t;
 
    while (t--) {
        ll n;
        cin >> n;
 
        ll ret = 0;
 
        while (n) {
            int nMod100 = n % 100;
 
            ret += dp[nMod100];
            n /= 100;
        }
 
        cout << ret << '\n';
    }
 
    return 0;
}
 
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[1563] 개근상  (0) 2017.07.24
[2225] 합 분해  (0) 2017.07.24
[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27

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


처음엔 on과 off인 부분을 나눠서

그리디로 접근을 하려고 했었는데

1-2로 가는데 5, 2-3으로 가는데 20

1-4로 가는데 10, 4-5로 가는데 5이고, YNNNN, p = 3이라면

1-4-5 루트가 나와야하는데 1-2-3 루트가 나옵니다.


짱돌을 엄청나게 굴렸지만.... 생각이 잘안났습니다.

그래서 분류를 봤는데

dp와 비트마스크로 해결하는 문제였습니다.


저는 2차원 dp로 해결했습니다.

dp[on 발전소 갯수][발전소의 상태]라고 정의했습니다.

사실 발전소의 상태로 발전소의 개수를 알 수 있지만 편의를 위해 이렇게 해결했습니다.


문제에서 적어도 p개라고 했는데 p개 초과일 경우가 p개인 경우보다 코스트가 작아지는 경우는 없으므로

탈출조건은 발전소 갯수가 p이상일 때 탈출시켰습니다.


아래는 코드입니다.

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
67
68
69
70
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 16
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][1 << 16];
int n, p;
int on;
int onCnt;
 
int f(int cnt, int on) {
    if (cnt >= p) return 0;
 
    int &ret = dp[cnt][on];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < n; i++) {
        if(on & 1 << i){
            for (int j = 0; j < n; j++) {
                if (i == j || on & (1 << j)) continue;
                ret = min(ret, f(cnt + 1, on | 1 << j) + spend[i][j]);
            }
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'Y') on |= 1 << i, onCnt++;
    }
 
    cin >> p;
 
    memset(dp, -1, sizeof(dp));
 
    int ret = f(onCnt, on);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2225] 합 분해  (0) 2017.07.24
[2158] 동전 교환  (0) 2017.07.09
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07

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



별 이상한 방법으로 엄청 시도했습니다..

dfs, bfs, 비트마스크 등등 ㅠㅠㅠㅠ....


해결 알고리즘은 플로이드-와샬을 이용하는 것입니다.


플로이드-와샬을 이용하면 모든 정점에 대한 최단거리를 테이블로 만들 수 있습니다.

잘모르시는 분들은 다른 블로그나 책을 통해서 공부하시고 참고해주시기 바랍니다.


input으로 들어오는 테이블이 현재 최단 거리 테이블이니

그 테이블을 기준으로 다시 한번 플로이드를 돌립니다.


이 때 중요한 것은

i - k - j(i에서 k를 거쳐 j로 가는 거리)가 i - j와 같다면

i - j간선, i - k간선, k-j간선 총 세개가 필요했던 것이

i - k, k - j 두 개의 간선으로 표현이 가능합니다.


플로이드를 통해서 이러한 간선을 전부 체크해준 후에

마지막에 체크되지 않은 간선 / 2 혹은 2차원 테이블에서 반만 더해준 후에 결과를 출력합니다.


-1이 출력되는 조건은 input으로 들어온 데이터가 최단거리가 아닐 때 입니다.


아래는 풀 코드입니다.


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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 200
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[20][20];
int n;
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    bool destroy[20][20] = { 0, };
    //플로이드
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j || i == k || k == j) continue;
                
                //삭제할 간선 찾기
                if (spend[i][j] == spend[i][k] + spend[k][j]) {
                    destroy[i][j] = 1;
                }
                //i, j가 최단거리가 아닐경우 -1 출력
                else if (spend[i][j] > spend[i][k] + spend[k][j]) {
                    puts("-1");
                    return 0;
                }
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            ret += !destroy[i][j] * spend[i][j];
        }
    }
 
    cout << ret;
 
    return 0;
}
cs


'알고리즘 > 최단 거리' 카테고리의 다른 글

[14588] Line Friends(small)  (0) 2017.07.23
[1686] 복날  (0) 2017.07.12

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


메모리 제한 8MB

n의 범위는 0<= n < 2^25


8MB는 약 2의 23승이므로

n의 범위만큼 배열을 만들 수 없습니다.


해쉬로 해결해보려했으나 N의 개수가 500만이여서 전부 저장할 수 없었습니다.


이 문제는 비트마스크로 해결할 수 있습니다.


핵심은 int가 32비트라는 점입니다.

int가 32비트이므로 비트를 32개 사용할 수 있는 것입니다.


n의 범위가 2^25이지만 몫을 배열의 인덱스로 사용하고 나머지를 해당 인덱스의 값에 비트로 저장하면 표현이 가능해집니다.



배열[ 입력받은 N / 2^5 ] = (N % 2^5) << 1

로 저장을 합니다.

그리고 존재하는지 검사를 할 때는 엔드 연산을 통해서 하면 되겠지요?


아래는 풀 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
 
int exist[(1 << 25) / 32];
int main() {
    int n;
 
    while (~scanf("%d", &n)) {
        int v = n / 32;
        int m = 1 << (n % 32);
 
        if (!(exist[v] & m)) {
            exist[v] += m;
            printf("%d ", n);
        }
    }
 
    return 0;
}
 

c


'알고리즘 > 비트마스크' 카테고리의 다른 글

[2064] IP 주소  (0) 2017.08.01
[1322] X와 K  (0) 2017.08.01

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



처음에 예제를 보고

같은 전구가 반복되는 pos부터

같은 전구가 또 반복되는 pos -1까지 반전시키면 된다고 생각했습니다.


예제의

1 1 0 0 1 0 1 1 1 0

의 예제에서


처음 1 1(pos 0, 1)이 반복됩니다. 

그래서 pos = 1 부터 그 다음에 0 0 이 반복되기 때문에 pos - 1까지의 구간을 반전시키면


1 0 1 0 1 0 1 1 1 0

7이 됩니다.


그 다음 다시 원상 복귀!

1 1 0 0 1 0 1 1 1 0에서

0 0 구간 (위에서 찾은 pos 값 즉.. 3!!!!! 인덱스를 말하는 것)

3부터 시작해서

또 반복되는 구간은

1 1 1

즉 인덱스(pos) 7입니다. 그럼 pos - 1까지 반전을 시켜야하므로

1 1 0 1 0 1 0 1 1 0

7이 됩니다.


마지막으로

1 1 1 구간에서 반복이 연속되므로  1 0 1을 바꿔주는 경우가 있습니다.

1 1 0 0 1 0 1 0 1 0

이것또한 7입니다.


즉 정답은 7입니다!!!!!!!


근데... 이렇게 푸니까 시간 초과..ㅠㅠㅠㅠㅠ


반전시키는 구간 길이가 n이면 n만큼의 시간이 걸릴테고..

구간을 찾는 것도 시간이 걸리고...

여러가지 이유로 시간이 초과됩니다...


n의 시간으로 해결할 수 있어야 할 것 같은데 방법이 잘 떠오르지 않았습니다.


문제의 해결 방법은


전구를 세 구간으로 나누는 것입니다.

이게 무슨 말이냐면


반전 시키는 구간을 O

아닌 구간을 X로 치면


O X X

X O X

X X O

로 구간을 나누면 된다는 말입니다.


구간을 나누는 기준은 같은 전구가 반복되는 pos입니다.


1 1 0 0 1 0 1 1 1 0

이 예제에서는 위에서 설명한 구간이겠지요.


이렇게 해서

배열에 같은 전구가 나올 때 까지의 번갈아가는 패턴의 값을 저장합니다.!


a[0] = 1;(인덱스 0에서 0구간)

a[1] = 2;(인덱스 1에서 2구간)

a[2] = 4;(인덱스 3에서 6구간)

a[3] = 1;(인덱스 7에서 7구간)

a[4] = 2;(인덱스 8에서 9구간)


이렇게 다섯개의 구간이 생성됩니다.


이 5개의 구간 중 연속된 3개를 더하면 최대 번갈아가는 패턴의 값이 나오겠지요!


아래는 정답 코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
int a[MAX_SIZE];
int n;
 
int main() {
 
    scanf("%d", &n);
 
    int before = -1;
    int pos = 1;
 
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        
        if (before == t) pos++;
        
        a[pos]++;
        before = t;
    }
 
    int ret = 0;
    for (int i = 1; i <= pos; i++) {
        ret = max(ret, a[i - 1] + a[i] + a[i + 1]);
    }
 
    printf("%d", ret);
 
    return 0;
}
 
cs


시간초과 코드입니다.
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 100000
 
using namespace std;
 
bool a[MAX_SIZE];
int n;
 
int cnt(int start, int end) {
    int before = -1;
    int ret = 0;
    int tmp = 0;
 
    bool flag = 0;
    for (int i = 0; i < n; i++) {
        if (start <= i && i <= end) {
            a[i] = !a[i];
            flag = 1;
        }
        if (before != a[i]) tmp++;
        else ret = max(ret, tmp), tmp = 1;
 
        before = a[i];
 
        if (flag) {
            flag = 0;
            a[i] = !a[i];
        }
    }
 
    return ret;
}
 
int f(int pos, int before) {
    int i;
 
    for (i = pos + 1; i < n; i++) {
        if (before == a[i]) {
            break;
        }
 
        before = a[i];
    }
 
    return cnt(pos, i - 1);
}
 
int main() {
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    
    int before = -1;
    int ret = cnt(-1, -1);
 
    for (int i = 0; i < n; i++) {
        if (before == a[i]) {
            ret = max(ret, f(i, a[i]));
        }
 
        before = a[i];
    }
 
    printf("%d", ret);
 
    return 0;
}
cs


'알고리즘 > 구현' 카테고리의 다른 글

[10986] 나머지 합  (0) 2017.07.24
[3474] 교수가 된 현우  (0) 2017.07.13
[14499] 주사위 굴리기  (0) 2017.04.16
[5624] 좋은 수  (0) 2017.04.06
[3190] 뱀  (0) 2017.04.05

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


3차원 dp문제입니다.


dp정의는

dp[인덱스][인접한 비트 수][현재 비트]라고 정의할 수 있습니다.


ex)

예제로 

n = 6이고 k=2일 때를 들어보겠습니다.

만약에 

dfs를 이용하여 0,1,1,1까지 들어와서 그다음에 깊이 6까지 들어갔다왔다고 생각해보면.


1. 00111-0

2. 00111-1


이렇게 2가지의 경우가 있겠죠

인접한 비트 수가 2인 경우는 1번하나겠죠!


근데 11011라는 수로 들어왔다고 칩시다!

그 다음으로 들어갈 필요가 있을까요??

아니요 없습니다!!


이유는 위의 00111경우에서


현재 인덱스가 5이고 인접한 비트 수가 2이고 현재 비트가 1인 경우에 1가지 밖에 없다는 것을 알았기 떄문에

굳이 다시 들어갈 필요가 없는 것입니다.

00111의 경우도

마찬가지로

11011-0과

11011-1

두가지 중 1번만 가능한 경우이기 때문입니다.


ret += f(d + 1, adj, 0);

ret += f(d + 1, adj + bit * 1, 1);


이 코드에서 윗 줄은 다음 비트가 0이기 때문에 다음으로 넘어갈때 인접한 비트 수가 증가할 수 없어서 특별한 연산 없이 adj를 삽입합니다.

두번째 줄은 내 비트가 1이기 때문에 현재 비트가 무엇이냐에 따라 인접한 비트 수가 증가할 수도 있고 그대로일 수도있겠죵! 그래서 두번째 같은 식이 나옵니다.


아래는 문제의 풀코드입니다.

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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 101
 
using namespace std;
int n, k;
int dp[MAX_SIZE][MAX_SIZE][2];
 
int f(int d, int adj, int bit) {
    if (d == n - 1) {
        if (adj == k) return 1;
        else return 0;
    }
 
    int &ret = dp[d][adj][bit];
    if (ret != -1) return ret;
    ret = 0;
 
    ret += f(d + 1, adj, 0);
    ret += f(d + 1, adj + bit * 1, 1);
 
    return ret;
}
 
int main() {
 
    int t;
    scanf("%d", &t);
 
    while (t--) {
        scanf("%d %d", &n, &k);
        memset(dp, -1, sizeof(dp));
 
        int ret = 0;
        for (int i = 0; i < 2; i++) {
            ret += f(0, 0, i);
        }
 
        printf("%d\n", ret);
    }
    return 0;
 
}
cs


'알고리즘 > 다이나믹 프로그래밍(DP)' 카테고리의 다른 글

[2158] 동전 교환  (0) 2017.07.09
[1102] 발전소  (0) 2017.07.08
[1029] 그림 교환  (0) 2017.06.27
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25

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



이분매칭으로 문제를 해결했습니다.


문제해결방법

1. 인풋으로 들어온 상어의 능력치 별로 간선을 만들어줍니다.

a가 b를 먹을 수 있다면 a의 간선에 b를 넣어줍니다.

이 문제의 핵심은 a==b인 경우입니다.(세 개의 능력치가 같은 경우)

이게 왜 중요하냐면

a가 b를 먹었는데

밑에서 b가 a를 또 먹을 수 있기 때문에 이것을 방지해야합니다.


가장 간단한 방법으로(사실 다른 방법따위 모름) 인덱스가 a < b인 경우에만 먹을 수 있게 하면 됩니다.(물론 같은경우에만)

이렇게 되면 a와 b가 능력치가 같을경우 a를 처리할떄 b를 먹을 것이고 b를 처리할 때는 a > b 이므로 먹을 수 없습니다.


2. 간선을 만든 후 상어는 각각 두마리씩 먹을 수 있습니다. 그러므로 한번 처리할떄 두번씩 먹어줍니다 

제가 계속 실수 했던 부분이

visit을 초기화안하고 먹고 또먹었습니다.


이렇게

1
2
3
4
5
6
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }

cs


이렇게 멤셋을 두번해줘야합니다!!!
이유는 아래의 예시를 보면서 설명하겠습니다.

이 그림은 현재
1번이 1번과 2번을 매칭했을 때
2번이 1번을 뺏어서 1번이 3번과 매칭된 상황입니다.
2번이 1번을 뺏으면서 visit[1]은 방문한 상태가 되겠죠??
근데 visit초기화를 안하면
2번이  2번에 매칭을 시도하면서 1번으로 들어가서 1-2를 미뤄내고 4번에 연결되어야하는데(1과 4사이에 선이 있다고 가정)
이미 방문했기 때문에 그냥 넘어가버리게 되죠!@

이게 핵심입니당!!

3. 마지막으로 B배열이 -1인 것을 카운트하여 출력하면 정답입니다.(-1라는 것은 매칭이 안된 것이므로 안죽음)

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 1000
 
using namespace std;
 
int B[MAX_SIZE];
bool visit[MAX_SIZE];
vector<int> edge[MAX_SIZE];
 
int sharkSize[MAX_SIZE];
int sharkIntel[MAX_SIZE];
int sharkSpeed[MAX_SIZE];
 
int n;
 
int eat(int a, int b) {
    int ret = 0;
    if (sharkSize[a] < sharkSize[b]) return 0;
    else if(sharkSize[a] == sharkSize[b]) ret++;
    if (sharkIntel[a] < sharkIntel[b]) return 0;
    else if (sharkIntel[a] == sharkIntel[b]) ret++;
    if (sharkSpeed[a] < sharkSpeed[b]) return 0;
    else if (sharkSpeed[a] == sharkSpeed[b]) ret++;
 
    if (ret == 3) return 2;
    return 1;
}
 
bool f(int from) {
    visit[from] = 1;
 
    for (int i = 0; i < edge[from].size(); i++) {
        int to = edge[from][i];
        if (B[to] == -1 || !visit[B[to]] && f(B[to])) {
            B[to] = from;
            return 1;
        }
    }
 
    return 0;
}
 
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &sharkSize[i], &sharkIntel[i], &sharkSpeed[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int eatFlag = eat(i, j);
 
            if (eatFlag == 1) edge[i].push_back(j); //먹을 수 있는경우
            else if (eatFlag == 2 && i < j) edge[i].push_back(j); // 능력치가 같은 경우
        }
    }
 
    memset(B, -1, sizeof(B));
    
    for (int i = 0; i < n; i++) {
        memset(visit, 0, sizeof(visit));
        f(i);
        memset(visit, 0, sizeof(visit));
        f(i);
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) if (B[i] == -1) ret++;
    printf("%d", ret);
 
    return 0;
}
cs





'알고리즘 > 네트워크 플로우' 카테고리의 다른 글

[12843] 복수전공  (0) 2017.08.24
[1017] 소수 쌍  (0) 2017.06.27
[6086] 최대유량  (1) 2017.06.03

+ Recent posts

티스토리툴바