728x90
난이도 : 골드3
풀이일 : 05066
https://www.acmicpc.net/problem/1516
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
풀이 코드
import sys
from collections import deque
N = int(sys.stdin.readline().strip())
time = [0] * N # 개별 건물 건설 시간
total = [0] * N # 개별 건물 누적 시간
count = [0] * N # 선행 건물 개수
building = [[] for _ in range(N)] # 선행 건물 종류
for i in range(N):
t, *temp = map(int, sys.stdin.readline().split())
time[i] = t
for j in temp: # -1 아닌 요소에 대해 선행 건물 정보 저장
if j > 0:
count[i] += 1
building[j-1].append(i)
queue = deque() # 선행 건물이 없다면, queue 추가, 시간 저장
for i in range(N):
if not count[i]:
queue.append(i)
total[i] = time[i]
while queue: # 건설 작업, 시간은 누적 시간 중 큰 값으로 재할당
x = queue.popleft()
for y in building[x]:
count[y] -= 1
total[y] = max(total[y], total[x] + time[y])
if not count[y]: # 선행건물이 모두 지어진 건물은 queue 추가
queue.append(y)
for i in total: # 모든 건물의 누적시간 출력
print(i)
코드 구성
- time : 개별 건물 건설 시간
- total : 개별 건물의 선행건물 건설 시간을 포함한 누적 건설 시간
- count : 선행 건물 개수
- building : 해당 건물을 선행 건물로 하는 건물 종류
- queue : 선행 건물이 없는 건물
- 정보 입력 받을 때, 요소의 개수가 제각각이므로 *패킹 연산자 사용
- 2차원 배열 building으로 남은 선행 건물 개수를 줄여나가며 누적 시간은 큰 값으로 재할당
- 선행 건물이 사라진 건물들은 queue 추가로 건설
느낀점
맨 처음 입력 받을 때, *패킹 연산자로 입력받은 temp를 사용해 count[i], building[j-1]을 정보를 저장할 때 대충 넘어가서 최종 출력을 해보고 안 맞는 부분을 고쳤다.
내가 하고 있는 작업에 대한 결과를 논리적으로 생각하고 접근해서 맞는지 꼼꼼하게 확인하는 과정을 거치자
'알고리즘 > 🥇 골드' 카테고리의 다른 글
백준 3665 최종순위 파이썬 풀이 (0) | 2023.05.08 |
---|---|
백준 9470 Strahler 순서 파이썬 풀이 (0) | 2023.05.07 |
백준 2056 작업 파이썬 풀이 (0) | 2023.05.05 |
백준 2252 줄세우기 파이썬 풀이 (0) | 2023.05.04 |
백준 1005 ACM Craft 파이썬 풀이 (0) | 2023.05.03 |