반응형
[백준] 1005번 ACM Craft - PYTHON https://www.acmicpc.net/problem/1005
알고리즘 분류
출력
건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.
건설순서는 모든 건물이 건설 가능하도록 주어진다.
제한
- 2 ≤ N ≤ 1000
- 1 ≤ K ≤ 100,000
- 1 ≤ X, Y, W ≤ N
- 0 ≤ Di ≤ 100,000, Di는 정수
>> 소스
import sys
from collections import deque
T = int(input(" 테스트 케이스 T 입력 : "))
for _ in range(T):
N,K=map(int,input(" 건물수, 건설 순서 : ").split())#건물수, 건설순서규칙
time=[0]+list(map(int,input(" 각 건물들의 건설시간 : ").split()))#건물들의 건설시간
seq=[[] for _ in range(N+1)]#건설순서규칙
inDegree=[0 for _ in range(N+1)]#진입차수
DP=[0 for _ in range(N+1)]#해당 건물까지 걸리는 시간
for _ in range(K):#건설순서규칙 저장
a,b=map(int,input(" 건설순서규칙 : ").split())
seq[a].append(b)
inDegree[b]+=1
q = deque()
for i in range(1,N+1):#진입차수 0인거 찾아서 큐에 넣기
if inDegree[i]==0:
q.append(i)
DP[i]=time[i]
while q:
a=q.popleft()
for i in seq[a]:
inDegree[i]-=1#진입차수 줄이고
DP[i]=max(DP[a]+time[i],DP[i])#DP를 이용해 건설비용 갱신
if inDegree[i]==0:
q.append(i)
ans = int(input(" W : "))
print(DP[ans])>> 결과
>> ./1005_ACM_Craft.py
테스트 케이스 T 입력 : 2
건물수, 건설 순서 : 4 4
각 건물들의 건설시간 : 10 1 100 10
건설순서규칙 : 1 2
건설순서규칙 : 1 3
건설순서규칙 : 2 4
건설순서규칙 : 3 4
W : 4
120
건물수, 건설 순서 : 8 8
각 건물들의 건설시간 : 10 20 1 5 8 7 1 43
건설순서규칙 : 1 2
건설순서규칙 : 1 3
건설순서규칙 : 2 4
건설순서규칙 : 2 5
건설순서규칙 : 3 6
건설순서규칙 : 5 7
건설순서규칙 : 6 7
건설순서규칙 : 7 8
W : 7
39반응형
'프로그래밍 > Baekjoon' 카테고리의 다른 글
| [백준] 1007번 벡터 매칭 - PYTHON vector matching (0) | 2023.02.16 |
|---|---|
| [백준] 1006번 습격자 초라기 - PYTHON, 점화식 (0) | 2023.02.11 |
| [백준] 1004번 어린완자 the Little Prince - PYTHON (0) | 2023.02.08 |
| [백준] 1003번 피보나치 fibonacci - PYTHON (0) | 2023.02.08 |
| [백준] 1002번 터렛 Turrets - PYTHON (0) | 2023.02.07 |
