[BOJ/Python] 16169_수행 시간

문제 출처:https://www.acmicpc.net/problem/16169

16169번: 수행 시간

문제

특정 임무를 수행하기 위해 n개의 컴퓨터로 이루어진 시스템이 있다고 하자. 이 시스템의 동작 체계는 아래와 같다.

1. 모든 컴퓨터는 1번부터 n번까지 번호가 매겨져 있다. 모든 컴퓨터는 각자의 계급과 동작 속도를 가지고 있다. 또한 계급과 동작 속도는 모두 양의 정수이다.
2. i번 컴퓨터와 j번 컴퓨터 간의 전송 시간은 (i - j)^2이다.
3. 각 n개의 컴퓨터의 계급은 c1, c2, … cn이다. (1 ≤ c1 ≤ c2 ≤ … ≤ cn ≤ n). 주어진 컴퓨터의 계급을 오름차순으로 정렬했을 경우, | cj -cj-1 |≤ 1이다. 
4. 제일 낮은 계급의 컴퓨터를 제외한 모든 컴퓨터들은 자신보다 한 단계 낮은 계급의 모든 컴퓨터에게 정보를 전달받아야만 동작을 시작 할 수 있다. 이 때, 동작을 시작하기 위해서는 그 컴퓨터의 동작 속도만큼의 시간이 소요된다.
5. 제일 낮은 계급의 컴퓨터는 전달 받을 정보가 없다. 따라서 시스템 시동과 동시에 동작한다.
6. 계급이 c인 컴퓨터가 동작을 마치면 c+1의 계급을 가진 모든 컴퓨터에 정보를 전달 후 종료된다.
7. 모든 컴퓨터가 동작을 마치고 종료되면 이 시스템의 임무 수행이 끝난다.
8. 가장 낮은 계급은 1이다.

이 시스템에 대한 정보가 주어졌을 때 임무 수행이 끝날 때까지 걸린 시간을 구하여라.

입력

첫 번째 줄에는 컴퓨터의 개수 n이 주어진다. (3 ≤ n ≤ 100) 두 번째 줄부터 n개의 줄에 걸쳐 1번부터 n번까지 각 컴퓨터의 계급과 동작 속도 t가 공백을 두고 주어진다. (1 ≤ t ≤ 100)

출력

문제의 정답을 출력하라.

예제 입력 1

9
1 1
3 9
3 1
4 2
4 2
2 5
1 30
4 2
5 3

예제 출력 1

103

---

풀이

 

 

1. 각 계급에서의 컴퓨터들은 동작을 마치고, 다음 단계의 컴퓨터들에게 정보를 전달한다.
2. 여기서 컴퓨터들이 동작하는데 드는 시간은 각 컴퓨터마다의 동작 속도 t이다.
3. 다음 단계의 컴퓨터들에게 정보를 전달하는데 드는 시간은 컴퓨터의 번호에 따라 다른데, i번 컴퓨터와 j번 컴퓨터 간의 전송의 경우 (i - j)^2 만큼의 시간이 걸린다.
4. 최종적으로 1단계에 있는 컴퓨터들부터 동작하여, 최종적으로 모든 컴퓨터들이 동작을 마쳤을 때 걸리는 시간을 출력하는 문제이다.

우선 코드는 다음과 같다.

 

import sys
 
def solve():
 
    for i in ranks[1]:
        total_time[i] = times[i]
    
    for i in range(1,n):
        for node in ranks[i]:
            for next in ranks[i+1]:
                total_time[next] = max(total_time[next],(next-node)**2 + total_time[node] + times[next])
 
 
n = int(sys.stdin.readline())
 
total_time = [0 for _ in range(n+1)]
times = [0]
ranks = [[] for _ in range(n+1)]
 
for i in range(1,n+1):
    rank,t = map(int,sys.stdin.readline().split())
    ranks[rank].append(i)
    times.append(t)
 
solve()
 
print(max(total_time))

 

• ranks의 경우, 각 계급에 존재하는 컴퓨터의 번호를 저장한다. ranks [1]의 경우, 계급이 1인 컴퓨터의 번호들이 저장된다.
• times의 경우, 각 컴퓨터들마다 동작하는 데 드는 동작시간 t의 정보가 저장된다. times [2]의 경우, 2번 컴퓨터의 동작시간이다.
• total_time은 해당 컴퓨터를 수행하는데 드는 총 소요시간이다.
• solve() 함수의 경우, 우선 계급이 1인 컴퓨터는 시스템의 시동과 동시에 시작되므로, 동작시간 t가 곧 해당 컴퓨터의 총 소요시간이다.
• 계급이 2 이상인 경우, 아래 계급이 동작한 이후에 동작한다.
• (next-node)**2 의 경우, node 번 컴퓨터와 next 번 컴퓨터의 전송시간이다.
• total_time [node]는 node 번 컴퓨터까지의 총 소요시간이고, times [next]는 next 번 컴퓨터의 동작시간이다.
• 따라서, (현재 컴퓨터까지의 총 소요시간 + 전송시간 + 다음 컴퓨터의 동작시간)을 나타내고, 이 값이 다음 컴퓨터의 총 소요시간보다 크다면 바꾸어준다.
• 최종적으로 제일 오래 걸리는 시간을 출력한다.