https://www.acmicpc.net/problem/16169
16169번: 수행 시간
첫 번째 줄에는 컴퓨터의 개수 n이 주어진다. (3 ≤ n ≤ 100) 두 번째 줄부터 n개의 줄에 걸쳐 1번부터 n번까지 각 컴퓨터의 계급과 동작 속도 t가 공백을 두고 주어진다. (1 ≤ t ≤ 100)
www.acmicpc.net
위상정렬로 접근한 문제다.
풀이
해당 문제의 컴퓨터는 자료를 전송할 다음 등급의 컴퓨터가 여러 대라면 동시에 자료를 전송하는 것으로 계산하면 된다. 즉 위상정렬을 통해 다음 등급의 컴퓨터를 탐색할 때, 간선의 비용이 최대 값인 경우만 찾아내면 된다.
입력되는 등급을 통해 위상정렬 순서를 구해 탐색을 수행한다. (다음 등급의 컴퓨터에게 자료를 전달하는 시간 + 다음 컴퓨터의 구동시간)의 최댓값을 저장할 ans 배열을 생성. 매 탐색마다 해당 배열을 최댓값으로 갱신하고 탐색이 종료된 후 ans 배열의 최댓값을 출력하면 정답이다.
예제를 기준으로 다음과 같이 수행된다.
가장 먼저 가장 낮은 등급의 컴퓨터인 1번과 7번 컴퓨터가 동작한다.
각자의 (동작시간 + 전송시간)의 값 중 가장 큰 값이 다음 등급인 6번 컴퓨터에게 전달되며,
해당 컴퓨터는 자신의 구동시간을 더해 ans배열에 갱신한다.
이후 탐색 큐에 6과 ans [6]의 값 36을 담아 다음 탐색을 수행한다.
2등급 컴퓨터인 6번 노드는 다음 등급의 컴퓨터인 2번과 3번 컴퓨터에 자료를 전송.
6번 컴퓨터의 대기시간 + 동작시간의 값 + 전송시간의 값이 전달된다.
이제 해당 값에 2번과 3번 컴퓨터의 구동시간을 더해 ans배열을 갱신한다.
각 노드로 진입하는 대기시간 + 구동시간 + 전송시간의 값 중 가장 큰 값을 입력받아 ans배열을 갱신해 나가면 된다.
구동시간에는 음수가 입력되지 않으므로 마지막 컴퓨터의 대기시간 + 구동시간 + 동작시간을 더해 출력하면 된다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [5719] 거의 최단 경로 (0) | 2023.04.30 |
|---|---|
| [1711] 직각삼각형 (0) | 2023.04.19 |
| [24526] 전화 돌리기 (0) | 2023.04.05 |
| [14907] 프로젝트 스케줄링 (0) | 2023.04.03 |
| [2637] 장난감 조립 (0) | 2023.04.01 |