휴가 나가기
문제
휴가가 얼마 남지 않은 용범이는 휴가를 나가기 전에 밀린 업무들을 처리하려고 한다.
그러나 모든 업무를 처리하기에는 시간이 부족하기 때문에 중요한 업무들만 처리하고 나가려고 한다.
용범이가 밀린 업무는 총 N개가 있고, 1번부터 N번까지 업무마다 번호가 매겨져 있다.
또한, 각 업무는 해당 업무를 처리하기 전에 먼저 처리해야 하는 선행 업무가 최대 1개 있을 수 있으며,
각 업무들의 선행 업무는 모두 다르다.
용범이는 한 번에 한 업무만 처리할 수 있기 때문에,
업무마다 중요도 w_i와 처리하는 데 걸리는 시간 t_i를 정리하고 어떻게 업무를 처리하는 것이 효율적인지 알아내려고 한다.
업무들을 처리하는 데 걸리는 시간은 처리한 업무들의 처리 시간의 합이다.
충분한 시간이 주어진다면 용범이는 모든 업무를 처리할 수 있지만, 휴가를 나가기까지 시간이 얼마 남지 않았다.
빨리 휴가를 나가고 싶어하는 용범이를 도와 처리한 업무들의 중요도 합이 S 이상이 되게 하는데 필요한 최소 시간을 구해주자.
입력
첫 번째 줄에 업무의 수 N과 처리한 업무들의 중요도 합의 최소 S가 공백으로 구분되어 정수로 주어진다.
(1 <= N <= 1000; 1 <= S <= 100000)
두 번째 줄에 각 업무의 중요도 w_1, w_2, …, w_N이 공백으로 구분되어 정수로 주어진다.
(1 <= w_i <= 100)
세 번째 줄에 각 업무의 처리 시간 t_1, t_2, …, t_N이 공백으로 구분되어 정수로 주어진다.
(1 <= t_i <= 1000)
네 번째 줄에 각 업무의 선행 업무 번호 p_1, p_2, …, p_N이 공백으로 구분되어 정수로 주어진다.
선행 업무의 번호가 0이면 선행 업무가 없는 것이다.
0이 아닌 모든 p_i들은 서로 다르다. (0 <= p_i <= N)
충분한 시간이 주어진다면 모든 업무를 처리할 수 있는 경우만 입력으로 주어진다.
출력
처리한 업무의 중요도의 합이 S이상이 되게 하는데 필요한 시간의 최솟값을 출력한다.
만약 모든 업무를 처리해도 중요도의 합이 S 미만이라면 -1 을 출력한다.
풀이
문제를 읽어보니 중요도 합이 S 이상이 되도록하는 최소 시간을 구하는 것이므로 냅색 문제라고 생각했는데
선행 업무가 있다는 조건이 특이했고, 간단하게 풀리지 않았다.
처음에는 BITSET으로 사전 작업이 이뤄졌는지 확인할까 했지만 쉽지 않았고
그러다가 선행 관계가 있는 업무들을 하나의 체인으로 묶는 아이디어를 생각했다.
만약 A 업무를 하려면 B를 먼저 해야 하고, B를 하려면 C를 먼저 해야 한다면,
C를 선택하는 순간 자동으로 B, A도 모두 처리해야 한다는 뜻이다.
그래서 선행 업무가 0인 것들을 루트로 해서 DFS로 트리를 탐색하며 체인들을 만들었다.
각 체인 내에서는 자식 업무를 선택하면 부모의 시간과 중요도가 누적되도록 했다.
예를 들어 1번 업무(w=3, t=5)의 선행 업무가 0이고, 2번 업무(w=4, t=6)의 선행 업무가 1이라면,
2번을 선택하면 1번도 해야 하므로 2번의 실제 중요도는 7, 실제 시간은 11이 되는 것이다.
이렇게 체인으로 묶고 나면 각 체인에서 하나의 업무만 선택하는 배낭 문제가 된다.
dp[i][j]를 i번째 체인까지 고려했을 때 중요도 j를 달성하는 최소 시간으로 정의하고,
각 체인의 업무들을 순회하며 선택하거나 선택하지 않는 경우를 따져서 DP 테이블을 채워나갔다.
체인들을 묶어서 뭉탱이로 놓고, 뭉탱이를 2차원 배낭 문제로 보고 풀 수 있었다.
중요도가 m 이상이 되면 저장할 필요가 없기 때문에 바로 ans를 업데이트 해준다.
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
101
102
103
104
105
106
107
108
109
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
using P=pair<ll,ll>;
long long mod = 1e9+7;
bool flag=0;
long long a, b, c, d;
long long n, m, t, k;
long long ans = 1e9;
int total=0;
cin >> n >> m; //n개로 m이상 채우기
vector<int> w(n+1);
vector<int> tt(n+1);
vector<int> pre(n+1);
int mung_c=0;
for(int i=1;i<=n;i++){
cin>>w[i];
total+=w[i];
}
for(int i=1;i<=n;i++){
cin>>tt[i];
}
vector<vector<int>> to(n+1);
for(int i=1;i<=n;i++){
cin>>pre[i];
if(pre[i]==0)mung_c++;
to[pre[i]].push_back(i);
}
if(total<m){
cout<<-1;
return 0;
}
//1, (1,2), (1,2,3), (1,2,4) 이렇게를 한뭉탱이로 묶어야함. 이 기준은 0이 될듯?
vector<vector<int>> mung(mung_c);
int x=0;
int tmp=0;
function <void(int, int)> dfs=[&](int dot, int mung_x){
for(int i=0;i<to[dot].size();i++){
mung[mung_x].push_back(to[dot][i]);
w[to[dot][i]]+=w[dot]; //시간이랑 가중치를 다 늘려. 왜냐면 얘를 반드시 전에 해야함.
tt[to[dot][i]]+=tt[dot];
dfs(to[dot][i], mung_x);
}
};
for(int i=1;i<=n;i++){
if(pre[i]==0){
mung[x].push_back(i);
dfs(i, x);
x++;
}
}
// for(int i=0;i<mung_c;i++){
// for(int j=0;j<mung[i].size();j++){
// cout<<mung[i][j]<<' ';
// }cout<<"\n";
// }
// for(int i=1;i<=n;i++)cout<<w[i]<<' ';
// cout<<'\n';
// for(int i=1;i<=n;i++){
// cout<<tt[i]<<' ';
// }cout<<'\n';
vector<vector<int>> dp(mung_c+1, vector<int>(m+1, 1e9));
for(int i=0;i<=mung_c;i++){
dp[i][0]=0;
}
for(int i=0;i<mung_c;i++){
for(int j=m;j>=0;j--){
for(int x=0;x<mung[i].size();x++){
dp[i+1][j]=min(dp[i+1][j], dp[i][j]);
if(dp[i][j]!=1e9){
if(j+w[mung[i][x]]>=m){
ans=min((int)ans, dp[i][j]+tt[mung[i][x]]);
// cout << "ans : " << ans << ' ' << dp[i][j] << ' ' << j
// << " wei : " << w[mung[i][x]] << ' ' << tt[mung[i][x]] << '\n';
}
}
if(j>=w[mung[i][x]] && dp[i][j-w[mung[i][x]]]!=1e9){
dp[i+1][j]=min(dp[i+1][j], dp[i][j-w[mung[i][x]]]+tt[mung[i][x]]);
}
}
}
}
//cout<<"mung_c : " << mung_c << '\n';
// for(int i=1;i<=mung_c;i++){
// for(int j=1;j<=m;j++){
// if(dp[i][j]==1e9)cout<<0<<' ';
// else cout<<dp[i][j]<<' ';
// }cout<<"\n";
// }
cout << ans;
return 0;
}