Baekjoon Online Judge #2056: 작업 (URL)
2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해
www.acmicpc.net
Problem (문제 원문)
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다.
각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.
몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다.
이 작업들은 번호가 아주 예쁘게 매겨져 있어서,
K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는
모두 1 이상 (K-1) 이하이다.
작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다.
(1번 작업이 항상 그러하다)
모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라.
물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.
Restrictions (제약사항)
시간 제한: 2초
메모리 제한: 256MB
Input (입력)
첫째 줄에 N이 주어진다.
두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.
Output (출력)
첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.
Examples (예제)
| Input | Output |
| 7 5 0 1 1 1 3 1 2 6 1 1 1 2 2 4 8 2 2 4 4 3 3 5 6 |
23 |
* Hint
- 1번 작업 : 0~5
- 2번 작업 : 5~6
- 3번 작업 : 6~9
- 4번 작업 : 5~11
- 5번 작업 : 11~12
- 6번 작업 : 11~19
- 7번 작업 : 19~23
Design (프로그램 설계)
Algorithm Category (알고리즘 분류)
Dynamin Programming (DP) (동적 프로그래밍) (URL)
[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍
Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다. - 특히 이러한 "작은 문제의 해답"을 Optima
dad-rock.tistory.com
Implementations (구현)
* GitHub (URL)
GitHub - ByeongHeonLee/Algorithms: Implementation of fundamental algorithms
Implementation of fundamental algorithms. Contribute to ByeongHeonLee/Algorithms development by creating an account on GitHub.
github.com
Data Structure (자료 구조)
| Data Structure | Type | Description |
| job_times[i] | C++ Built-in Array | - i번째 작업을 수행하는 데 소요되는 시간(Turnaround Time) |
| predecessors[i] | C++ Vector | - i번째 작업이 수행되기 위해 수반되어야 하는 작업들 |
| opt_times[i] | C++ Built-in Array | - i번째 작업이 가능한 한 빨리 완료되었다고 할때, 그 때의 종료시간 (즉, 이들 중 최댓값이 이 문제의 정답이다.) |
Performance (성능)
성공..!
Baekjoon Online Judge #2056: 작업 (URL)
2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해
www.acmicpc.net
Problem (문제 원문)
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다.
각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.
몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다.
이 작업들은 번호가 아주 예쁘게 매겨져 있어서,
K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는
모두 1 이상 (K-1) 이하이다.
작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다.
(1번 작업이 항상 그러하다)
모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라.
물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.
Restrictions (제약사항)
시간 제한: 2초
메모리 제한: 256MB
Input (입력)
첫째 줄에 N이 주어진다.
두 번째 줄부터 N+1번째 줄까지 N개의 줄이 주어진다. 2번째 줄은 1번 작업, 3번째 줄은 2번 작업, ..., N+1번째 줄은 N번 작업을 각각 나타낸다. 각 줄의 처음에는, 해당 작업에 걸리는 시간이 먼저 주어지고, 그 다음에 그 작업에 대해 선행 관계에 있는 작업들의 개수(0 ≤ 개수 ≤ 100)가 주어진다. 그리고 선행 관계에 있는 작업들의 번호가 주어진다.
Output (출력)
첫째 줄에 모든 작업을 완료하기 위한 최소 시간을 출력한다.
Examples (예제)
| Input | Output |
| 7 5 0 1 1 1 3 1 2 6 1 1 1 2 2 4 8 2 2 4 4 3 3 5 6 |
23 |
* Hint
- 1번 작업 : 0~5
- 2번 작업 : 5~6
- 3번 작업 : 6~9
- 4번 작업 : 5~11
- 5번 작업 : 11~12
- 6번 작업 : 11~19
- 7번 작업 : 19~23
Design (프로그램 설계)
Algorithm Category (알고리즘 분류)
Dynamin Programming (DP) (동적 프로그래밍) (URL)
[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍
Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다. - 특히 이러한 "작은 문제의 해답"을 Optima
dad-rock.tistory.com
Implementations (구현)
* GitHub (URL)
GitHub - ByeongHeonLee/Algorithms: Implementation of fundamental algorithms
Implementation of fundamental algorithms. Contribute to ByeongHeonLee/Algorithms development by creating an account on GitHub.
github.com
Data Structure (자료 구조)
| Data Structure | Type | Description |
| job_times[i] | C++ Built-in Array | - i번째 작업을 수행하는 데 소요되는 시간(Turnaround Time) |
| predecessors[i] | C++ Vector | - i번째 작업이 수행되기 위해 수반되어야 하는 작업들 |
| opt_times[i] | C++ Built-in Array | - i번째 작업이 가능한 한 빨리 완료되었다고 할때, 그 때의 종료시간 (즉, 이들 중 최댓값이 이 문제의 정답이다.) |
Performance (성능)
성공..!
