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 != -1) return 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, -1, sizeof(dp));
chk = (1 << N) - 1;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(0, 0) << '\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 != -1) return 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, -1, sizeof(dp));
chk = (1 << N) - 1;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
cout << func(0, 0) << '\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 |