728x90 위상 정렬3 [JAVA]백준 1516번: 게임 개발 www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 1. 문제 설명 어떤 건물을 짓기 전에 그 건물을 짓기 전에 지어야 하는 건물들을 지은 후에 지을 수 있다. 여러 개의 건물을 동시에 지을 수 있고, 건물을 짓는 명령을 내리기까지 시간이 걸리지 않는다고 하고, 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어질 때, 각 건물이 완성되기까지 걸리는 최소 시간을 출력하는 문제이다. 2. 풀이 백준 2056번 .. 2021. 3. 13. [JAVA]백준 2056번: 작업 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. 문제 설명 수행해야 할 작업 N개와 각각의 작업마다 걸리는 시간, 어떤 작업 X를 수행하기 전에 반드시 먼저 완료되어야 할 작업들이 주어졌을 때 모든 작업을 완료하기 위해 필요한 최소 시간을 구하는 문제. 2. 풀이 kwoncorin.tistory.com/75 [JAVA]백준 14567번: 선수과목 (Prerequisite) www.acmicpc.net/problem/14567 14567번: 선수.. 2021. 2. 25. [JAVA]백준 14567번: 선수과목 (Prerequisite) www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 1. 문제 설명 과목들의 선수과목 조건들이 주어질 때 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 구하는 문제. 2. 풀이 위상 정렬과 다이내믹 프로그래밍으로 풀 수 있는 문제이다. 1) 다이내믹 프로그래밍 X번 과목이 이수할 수 있는 최소 학기를 dp [X]라 할 때 dp [X]는 X의 선수과목들의 최소 학기의 최댓값 +1이다. dp [X]=MAX(dp [Y]+1) (Y는 X의 선수과목) 점화식과 선수과목 조건 A .. 2021. 2. 22. 이전 1 다음 728x90
