문제 링크입니다: www.acmicpc.net/problem/2056
2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해
www.acmicpc.net
N: 수행해야할 작업 -> 범위: 3 <= N <= 10,000
작업마다 걸리는 시간 -> 범위: 1 ~ 100
inDegree: 선행해야할 작업의 수를 저장하는 배열
graph: 작업 단방향 그래프를 나타내는 벡터 배열
result: 최소 시간
delay: 각 작업마다 걸리는 시간을 저장하는 배열
cache: 해당 작업이 완료되는데 걸린 최소 시간을 저장하는 배열
알고리즘
1. 작업들을 입력받으면서 graph, delay, inDegree 배열 업데이트
2. inDegree가 없는 작업들 큐에 추가
-> 이 때, cache[i] = delay[i]
3. 위상정렬을 진행하며 cache 업데이트
-> max(cache[next], cache[job] + delay[next])
4. cache 최댓값을 출력하고 프로그램 종료
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2157번 여행 (0) | 2021.01.27 |
|---|---|
| 백준 3954번 Brainf**k 인터프리터 (2) | 2021.01.19 |
| 백준 11657번 타임머신 (0) | 2020.12.10 |
| 알고리즘을 풀 때 런타임 에러가 발생하는 이유 (0) | 2020.11.05 |
| 백준 10837번 동전 게임 (0) | 2020.09.03 |