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

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



처음에 행렬 크기도 작고 dfs로 해결하면 끝이겠다 싶었습니다.

하지만.. 예제케이스를보면 ㅜ 모양 등 dfs로는 만들 수 없는 모양이 존재했습니다..


짱돌을 아무리 굴려도 해결할 수 없는..ㅠㅠ

블로그를 참조했습니다.


해결방법은 행렬이 작다는 것을 이용한 아이디어였습니다.

어떻게 이용하냐!


하면...


결국 25칸의 학생들 중에 7명을 고르면 된다는 점입니다!(다른 분은 어떻게 푸셨는지 모르겠음.. 아이디어만 스틸해옴..)


저는 그래서 dfs를 이용하여 학생들을 선택할 수 있는 모든 방법을 만들었습니다.

1번~25번까지의 학생이 있다고 생각하면 !

1,2,3,4,5,6,7

1,2,3,4,5,6,8

..

...

19,20,21,22,23,24,25

까지의 경우가 있겠죠!


이 모든 경우의 수는 25C7 입니다.


이렇게  dfs를 이용해서 깊이가 7 즉 7명의 학생까지 선택하면!

dfs의 매개변수에 S에 다솜파가 몇명인지를 계속 넘겨줍니다!

만약에 다솜파가 4명 이상이면! dfs로 선택한 7명이 전부 연결되어있는지를 확인합니다.!!!

그래서 전부 연결되어있다면 1을 리턴하여 카운트. 아니면 0을 리턴합니다.!


아래는 코드입니다.

궁금한 점은 댓글 달아주세요~~



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
89
90
91
92
93
94
95
96
97
98
99
100
#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 5
 
using namespace std;
 
char map[MAX_SIZE][MAX_SIZE];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int visit;
 
pair<int, int> toPos(int num) {
    return make_pair(num / 5, num % 5);
}
 
int toNum(pair<int, int> pos) {
    return pos.first * 5 + pos.second;
}
 
//내가 선택한 7명이 연결되어있는지를 확인하는 함수
bool exploration(int state, pair<int, int> pos) {
    visit |= 1 << toNum(pos); // 전역 변수 visit에 해당 학생을 쉬프트하여 체크
    if (state == visit) return 1; //isConnected에서 넘겨받은 state와 exploration으로 방문한 학생이 같으면 리턴 1
 
    bool ret = 0;
 
    for (int i = 0; i < 4; i++) {
        pair<int, int> npos = make_pair(pos.first + dx[i], pos.second + dy[i]);
 
        if (npos.first < 0 || npos.second < 0 || npos.first >= 5 || npos.second >= 5) continue;
        
        int nNum = toNum(npos);
 
        if (visit & (1 << nNum)) continue;
        if ((1 << nNum) & state) ret = max(ret, exploration(state, npos));
    }
    return ret;
}
 
//전부 연결되어있다면 1을 아니라면 0을 리턴하는 함수
bool isConnected(int state) {
    pair<int, int> now;
    
    //포문을 이용하여 내가 선택한 7명 중 한명을 찾아 탐색의 시작점으로 선택
    for (int i = 0; i < 25; i++) {
        if ((1 << i) & state) {
            now = toPos(i);
            visit = 1 << i;
            break;
        }
    }
    
    return exploration(state, now);
}
 
//dfs를 이용하여 25명의 학생 중 7명을 고르는 함수
int f(int num, int d, int state, int sCnt) {
    if (d == 7) {
        if (sCnt >= 4) return isConnected(state);
        else return 0;
    }
    int ret = 0;
 
    for (int i = num + 1; i < 25; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, d + 1, state | (1 << i), map[pos.first][pos.second] == 'S' ? sCnt + 1 : sCnt);
    }
 
    return ret;
}
 
int main() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    int ret = 0;
    for (int i = 0; i < 25 - 6; i++) {
        pair<int, int> pos = toPos(i);
        ret += f(i, 1, 1 << i, map[pos.first][pos.second] == 'S' ? 1 : 0);
    }
    printf("%d", ret);
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[10974] 모든 순열  (2) 2017.07.27
[1058] 친구  (0) 2017.07.20
[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18

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



처음엔 이분 매칭 문제인 것을 모르고..

엄청나게 틀렸네요... 시간초과 + 구현실수....


알고나서도 한참을 해맸는데요!

첫번째 이유는 첫번째 수와 매칭되는 수를 출력한다는 점이었어요..


소수 쌍을 구하는 것이기 때문에

홀수 + 홀수 = 짝수(2를 제외하고는 무조건 소수가 안됨)

짝수 + 짝수 = 짝수(무조건 안됨)

홀수 + 짝수 = 홀수(가능성 있음)

입니다!


그렇기 때문에 그룹을 홀수와 짝수로 나누어야하는데요!


첫번쨰 수가 홀수일수 도있고 짝수일 수도 있기 때문에 어떻게 진행해야할지 난해했습니다.

두번째 소수를 구하는 방법입니다. 풀고나니깐 뭐.. 에라토스테네스의 체를 써도 되고 그냥 나눠서 확인해도

입력받는 수가 1000까지기 때문에 최대 1999(두 수를 합쳐야하므로)밖에 안되서 오래걸리진 않습니다.


마지막으로 출력입니다. 입력이 정렬되서 들어온다는 말은 없으므로 출력할 때 정렬을 해야합니다.

저같은 경우는 우선순위 큐에 넣어서 그냥 큐가 빌때까지 출력했습니다.

-1이 출력되는 조건은 큐가 비어있다면 -1을 출력했습니다.


문제 해결 전략은

1. 첫번째 수와 다른 그룹의 수와 매칭을 시킨다.

2. 1에서 매칭된 수가 소수라면 1에서 매칭된 쌍을 제외하고 이분매칭 알고리즘을 이용해서 나머지를 매칭합니다.

3. 만약 전부 매칭해서 매칭 된 수가 입력 받은 N의 절반이 된다면 전부 매칭된 것이므로 우선순위 큐에다가 처음에 첫번째 수와 매칭한 수를 푸시해줍니다.

4. 위의 과정을 다른 그룹의 수의 개수만큼 반복합니다.


아래는 코드입니다.

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
89
90
91
92
93
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 50
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int arrA[MAX_SIZE];
int arrB[MAX_SIZE];
int pick;
int idxA, idxB;
 
int matchA[MAX_SIZE];
int matchB[MAX_SIZE];
bool visit[MAX_SIZE];
 
bool isPrime(int a) {
    if (a == 1) return 0;
    else if (a != 2 && a % 2 == 0) return 0;
    
    for (int i = 3; i * i <= a; i += 2) {
        if (a % i == 0) return 0;
    }
 
    return 1;
}
 
bool f(int idx) {
    if (visit[idx]) return 0;
    visit[idx] = 1;
 
    for (int i = 0; i < idxB; i++) {
        if (i == pick) continue;
 
        if (isPrime(arrA[idx] + arrB[i]) && (matchB[i] == -1 || !visit[matchB[i]] && f(matchB[i]))) {
            matchB[i] = idx;
            matchA[idx] = i;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    int arr[MAX_SIZE];
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    for (int i = 0; i < n; i++) {
        if (arr[0] % 2 == arr[i] % 2) arrA[idxA++] = arr[i];
        else arrB[idxB++] = arr[i];
    }
 
    priority_queue<int> pq;
 
    for (int i = 0; i < idxB; i++) {
        if (isPrime(arrA[0] + arrB[i])) {
            pick = i;
            
            int cnt = 1;
            memset(matchA, -1, sizeof(matchA));
            memset(matchB, -1, sizeof(matchB));
 
            for (int j = 1; j < idxA; j++) {
                memset(visit, 0, sizeof(visit));
                if (f(j)) cnt++;
            }
 
            if (cnt == n / 2) pq.push(-arrB[i]);
        }
    }
 
    if (pq.empty()) puts("-1");
    else {
        while (!pq.empty()) {
            printf("%d ", -pq.top()), pq.pop();
        }
    }
 
    return 0;
}
cs


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

[12843] 복수전공  (0) 2017.08.24
[1671] 상어의 저녁식사  (0) 2017.07.02
[6086] 최대유량  (1) 2017.06.03

+ Recent posts

티스토리툴바