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

 

1311번: 할 일 정하기 1

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매

www.acmicpc.net

외판원 문제를 풀때는 dp + 비트마스킹에 적응을 못했어서 푸는데 어려움이 많았지만 이번 문제는 좀 수월하게 했던것 같습니다..

 

dp[x][cost] : x번 사람이 고를 때 x - 1번째 사람까지 골랐던 일의 상태가 cost인 비용의 최솟값

여기서 cost에 비트마스킹을 이용합니다. (N = 20이므로 약 100만 정도의 크기입니다.)

 

저는 번호를 0 ~ N - 1로 두었기때문에 0번 사람부터 차례로 0 ~ N - 1번 일까지 돌면서 고르지 않은 일만 선택하였고,

x가 N일 때 모든 사람이 일을 골랐으면 0, 아니면 INF을 리턴하였습니다.

 

 

+ 음.. 시간과 메모리가 적게 나온 분의 풀이를 보았는데 dp[x][cost]가 아닌 dp[cost]만으로도 해결이 됐습니다..

dp[cost] : 고른 일의 상태가 cost일 때 비용의 최솟값

으로 두고 해결하면 될 것 같습니다! (소스는 같이 올리겠습니다)

 

역시 1차원 배열로 한 것이 시간적으로나 메모리적으로나 많은 이득을 가져갑니다..

 

 

[2차원 배열]

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[MAX][1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[x][cost];
    if (ret != -1return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(00<< '\n';
 
    return 0;
}
cs

 

 

[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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[cost];
    if (ret != -1return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(00<< '\n';
 
    return 0;
}
cs

'algorithm > dp' 카테고리의 다른 글

boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19

+ Recent posts