tose33

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 이전에 풀었던 ACM craft 처럼 위상 정렬과, DP를 써야하는 문제. (https://tose33.tistory.com/781) d[i] = i 노드 건물 완공하는데 걸리는 최소 시간

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 어제에 이어서 위상정렬 문제를 풀어봤다. 위상정렬 알고리즘을 실행하면 되는데, 중복되는 노드 번호가 주어진다는 것이 조금 다르다. bool형 배열을 만들고 이미 사용한 노드는 기록해서, 사용했다면 큐에 넣지 않으면 된다. 위상정렬 알고리즘에서는 루프가 노드수 만큼 돌기전에 큐가 비어버리면 더 이상 정렬이 불가능한데, 이 문제에서는 N 즉 가수의 수 만큼 루프를 돌기전에 큐가 비..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 크루스칼 알고리즘으로 MST를 만들고, MST에서 가중치가 가장 큰 간선을 빼주면 문제에서 원하는 두 개의 그래프가 된다.

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1년전인가 연구소2를 풀때, dfs로 N개의 바이러스 위치 중 M개의 바이러스 위치를 조합으로 선택하는걸 못해서 못풀었던 기억이 있는데 이제 그 부분은 아주 쉽게 해결했다. 그런데 이 문제는 활성, 비활성 바이러스의 차이를 생각하는데 꽤 오래 걸렸다..