유자의 코딩모험

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. 위의 예시를 보자. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 동시에 진행할 수 있다. 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다. 따라서 4번 건물의 건설을 완료하기 위해서는 10초 + 100초 + 10초 = 120초가 소요된다. 120초가 4번 건물을 가장 빨리 지을 때까지 걸리는 최소시간인 것이다. 건물 ..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제풀이 이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다. dp[i] = i번 건물을 건설 완료하는데 드는 최소 시간 최소 시간을 찾는 것이지만 선행 건물들이 모두 건설완료가 되어야하므로 최댓값을 찾는 것이다. 처음에 선행 정점을 가지지 않는 정점을 큐에 삽입할 때는 dp[i] = t[i]로 초기화해준다. 그리고 나서 다음 순서를 진행할 때 앞순서 건물 건설시간 + 현재 건물 건설시간이 최대인 것을 저장해주면 해당 건물을 건설완료 하는데 드는..