문제 : https://www.acmicpc.net/problem/30208
난이도 : P5
풀이
우선순위 제거
각각의 일은 우선순위 작업이 없거나 1개가 존재한다.
우선순위를 계산하면서 kanpsack을 하기엔 복잡하므로 우선순위를 제거한다.
먼저, 예제 1번을 예로들어
7 7
2 3 1 4 5 1 3
3 4 2 8 6 1 2
0 1 2 0 4 0 0로 입력이 제공될 경우,
- 1,4,6,7번은 우선순위 작업이 필요없음
- 2번은 1번을 먼저 작업해야함
- 3번은 2번을 먼저 작업해야함
--> 1,2번을 해야 3번을 할 수 있다. - 5번은 4번을 먼저 작업해야함
위를 응용하면 3번작업을 수행했다고 가정할때, 1번과 2번작업또한 수행했다는 결과가 나온다.
이를 이용해 우선순위 작업이 있는 작업들은 해당 작업을 수행하는데 필요한 우선순위 작업들의 w와 t를 합쳐주어 w와 t리스트를 갱신시켜준다.
아래처럼 w와 t를 갱신(ex. 3번작업을 수행한다는 것은 1,2번 작업을 했다는 뜻이므로, 해당 작업들의 w와 t를 3번 작업에 합쳐준다)
7 7 w : 2 3 1 4 5 1 3 t : 3 4 2 8 6 1 2 p : 0 1 2 0 4 0 0 --> w : 2 5 6 4 9 1 3 t : 3 7 9 8 14 1 2
그룹 묶기
위처럼 w와 t가 갱신되었다면, 이제 그룹을 묶을 차례이다.
우선순위가 제거된 현재 작업에서는 1번,2번,3번 작업을 2개이상 처리할 수 없다.(2번작업에는 1번작업이 포함되어 있고, 3번작업에는 1,2번 작업이 포함되어 있으므로)
그러므로, 기존의 부모노드격인 1,4,6,7(우선순위가 없는 작업들)에 파생되는 작업들을 하나로 묶어준다.
자기자신도 포함시켜준다.
1번작업의 파생작업 : 1,2,3 4번작업의 파생작업 : 4,5 6번작업의 파생작업 : 6 7번작업의 파생작업 : 7
knapsack 알고리즘
기존의 knapsack 알고리즘(1차원 dp이용)의 시간복잡도는 아래와 같다.
O(N*M), N: 배낭용량, N: 넣을 물건들
하지만 주어진 중요도(배낭용량)의 최대값이 100,000이고 작업의 수(넣을 물건들)이 1,000이므로 시간복잡도를 고려해, dp를 dictionary로 선언하여 갱신시켜준다.
초기 dp를 선언해주고, n번 작업의 파생작업에 대해 for문 작업시마다 임시 dictionary를 선언하여 사용한다. dp for문을 돌면서 item이 추가되기 때문이다.
반복문을 돌면서 갱신되는 업무중요도가 S이상이 될 경우, 결과값을 갱신시켜주고 dp배열에는 추가하지 않는다(의미가 없다. 중요도가 S 이상만 넘을때의 최소 시간을 계산해야 하므로)
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
N,S=map(int,input().split())
res=10**9
w=[0]+list(map(int,input().split()))
t=[0]+list(map(int,input().split()))
p=[0]+list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
dic={}
for i in range(1,N+1):
graph[p[i]].append(i)
def func(now,time,work,parent):
if parent!=0:
if parent in dic:
dic[parent].append(now)
else:
dic[parent]=[now]
w[now]+=work
t[now]+=time
for i in graph[now]:
func(i,t[now],w[now],i if parent==0 else parent)
func(0,0,0,0)
dp={}
for _,jobs in dic.items():
tmp={}
for job in jobs:
for work,time in dp.items():
total_work=work+w[job]
total_time=time+t[job]
if total_work<S:
if total_work in tmp:
tmp[total_work]=min(total_time,tmp[total_work])
else:
tmp[total_work]=total_time
else:
res=min(res,total_time)
if w[job]<S:
if w[job] in tmp:
tmp[w[job]]=min(tmp[w[job]],t[job])
else:
tmp[w[job]]=t[job]
else:
res=min(res,t[job])
for work,time in tmp.items():
if work in dp:
dp[work]=min(dp[work],tmp[work])
else:
dp[work]=tmp[work]
print(res if res!=10**9 else -1)