문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 방법 1005번 ACM Craft와 비슷한 문제다. 위상 정렬과 DP를 활용하는 문제이므로 잘 모르겠다면 위 링크를 통해 설명을 보는 것을 추천한다. 위 문제와 차이점은 입력 형식이 다르다는 점, 모든 건물의 건설 완성 시간을 출력해야 하는 점이다. 코드 #include #include #include #include using namespace std; int main() ..
위상 정렬
문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 방법 위상 정렬과 DP에 대해 알고 있어야 하는 문제다. 잘 모르겠다면 바킹독님 블로그나 라이님 블로그를 봐보자. (실제로 내가 알고리즘 공부를 하며 계속 방문중인 블로그들이다.) 건설 순서에 따라 위상 정렬을 진행해주면서 각 건물의 최소 건설 시작 시간을 갱신해주면 된다. 다시 말해, dp[i] = i번 건물을 짓기 시작하는 데 걸리는 최소 시간(최소 건설 시작 시간), buil..
