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


기본적으로 네트워크 이론이 좀 필요한 문제입니다.


서브넷 마스크 & ip 주소 = 네트워크 주소


라는 것을 알아야하며..

가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

라는 조건이 중요합니다.


모든 ip에 대해서 공통된 부분을 찾습니다.

모든 ip에 대해서 공통된 부분(왼쪽 비트 부터 시작해서 오른쪽 비트로 갈 때)

만약 다른 부분이 있으면 멈춰야합니다.


ip에서 네트워크 주소나 서브넷을 따질 때

nnnn.nnnn.nnnn.nnhh

이런식으로 n은 이어져야합니다.(n은 네트워크 h는 호스트)


무튼... 기본 이론은 이러합니당..


공통된 부분은 전부 1로 가득채워서 서브넷 마스크를 구하면

서브넷 마스크 & 임의의 ip주소 = 네트워크 주소 를 출력할 수 있습니다.


코드입니다.


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 <iostream>
#include <cstdio>
 
using namespace std;
 
int ip[1000];
 
void print(int mask) {
    int shift = 24;
    for (int i = 0; i < 4; i++, shift -= 8) {
        cout << ((mask >> shift) & (1 << 8) - 1);
        if (i != 3) cout << '.';
    }
    cout << '\n';
}
 
int main() {
    int n;
    cin >> n;
 
    //ip입력받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            int a;
            cin >> a;
            ip[i] <<= 8;
            ip[i] |= a;
            getchar();
        }
    }
 
    //서브넷
    int subnet = 0;
 
    //0번째 ip와 틀린부분 찾기
    //찾으면 탈출해서 틀린부분 전까지는 전부 1로 채우기.
    for (int i = 31; i >= 0; i--) {
        int bit = 1 << i;
        bool end = 0;
 
        for (int j = 1; j < n; j++) {
            if ((ip[0] & bit) != (ip[j] & bit)) {
                end = 1;
                break;
            }
        }
 
        if (end) break;
        else subnet |= bit;
    }
 
    //네트워크 주소 출력하기
    print(ip[0] & subnet);
    //서브넷 주소 출력하기
    print(subnet);
 
    return 0;
}
cs


저작자표시

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

[1322] X와 K  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

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


범위 안보고 그냥 풀었다가 시간초과...ㅎㅎㅎㅎ...

K값이 20억까지인데 그렇다면 K의 시간으로는 해결할 수 없습니다.


X + Y = X | Y

+연산과 OR연산이 같을 조건은

생각해보면 금방 알 수 있습니다.


OR은

0 0 0

0 1 1

1 0 1

1 1 1


입니다.


그러므로 X를 비트로 바꿨을 때 0인 digit??을 1로 바꿔준다면 같아질 수 있습니다.


예를 들어 보겠습니다.


1001(9)라는 수가 있습니다.

이 이진수에 2 혹은 4 혹은 6 등등을 더하면 덧셈과 OR연산이 같아지는 것을 볼 수 있습니다.

2 -> 10

4 -> 100

6 -> 110


아 그렇다면 0인 부분(부분? 자리??)에서 K번째 수를 찾으면 된다는 이야기입니다.


위에서 예를들면 K = 1이면 2가 되고, 2라면 4가 됩니다. 3이라면 6이됩니다.

4라면 16이 되겠지요.


00000000000000000000001001이라는 수는 9인데 이 비트들에서 1을 제외하고 K번쨰 수 인 값을 찾으면 되는 것입니다.


주의할 것은 쉬프트 연산을 할 때 롱롱으로 캐스팅하는 것을 잊으면 안됩니다.(엄청 틀렸음..ㅠㅠ)


코드입니다.


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 <cstdio>
 
using namespace std;
 
int main() {
    long long x, k;
    cin >> x >> k;
 
    bool binX[64] = { 0, };
    bool binK[64] = { 0, };
 
    int i = 0;
 
    //2진수로 바꿔서 배열에 저장(2진수 리버스임)
    while (x || k) {
        binX[i] = x % 2;
        binK[i] = k % 2;
        x /= 2;
        k /= 2;
        i++;
    }
 
    int ki = 0;
    int xi = 0;
    long long ret = 0;
 
    while (ki < i) {
        //0인 비트를 해당 자리 수 만큼 쉬프트한다.
        if (binX[xi] == 0) {
            ret |= (1LL << xi) * binK[ki++];
        }
        xi++;
    }
    
    cout << ret;
    
    return 0;
}
 
 
cs


저작자표시

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

[2064] IP 주소  (0) 2017.08.01
[13701] 중복 제거  (1) 2017.07.06

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/1029



처음에 dfs로 방문체크를 하면서 cost가 크거나 같으면 이동하는 식으로 해서 해결해보려고 했으나

65프로에서 시간초과가 뜨더군요.

제한시간이 2초인데

dfs로 하면 최악의 경우 15!의 시간이 걸리기 때문에 해결할 수 없었습니다.


그래서 dp를 이용해야 했는데..

방문한 곳의 상태가 필요했기 때문에 비트마스크를 사용했습니다.


제 dp의 정의는


dp[1 << 15][15][10] : 방문상태, 아티스트 번호, 비용으로 정의했습니다.


아래는 코드입니다.


f함수의 매개변수는 방문상태, 아티스트 번호, 코스트, 깊이 입니다.



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
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
 
#define ll long long
#define MAX_SIZE 15
#define INF 987654321
#define MOD 1000000
using namespace std;
 
int dp[1 << MAX_SIZE][MAX_SIZE][10]; //state, artistNumber, cost
int cost[MAX_SIZE][MAX_SIZE];
int n;
 
int f(int state, int artist, int c, int d) {
    int &ret = dp[state][artist][c];
    if (ret != 0) return ret;
    ret = d;
 
    for (int i = 0; i < n; i++) {
        if (state & (1 << i) || cost[artist][i] < c) continue;
        ret = max(ret, f(state | (1 << i), i, cost[artist][i], d + 1));
    }
    return ret;
}
 
int main() {
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &cost[i][j]);
        }
    }
 
    printf("%d", f(1, 0, 0, 1));
    
    return 0;
}
cs


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

[1102] 발전소  (0) 2017.07.08
[2698] 인접한 비트의 개수  (0) 2017.07.04
[1915] 가장 큰 정사각형  (0) 2017.06.07
[2629] 양팔 저울  (0) 2017.04.25
[2133] 타일 채우기  (0) 2017.04.20

+ Recent posts

티스토리툴바