백준 1005번
문제 풀이
작업의 우선순위가 정해져 있으므로
위상정렬을 사용하면 된다.
특정 건물을 짓는 시간을 최소한으로 하기위해서는
동시에 지어질 수 있는 건물들은 동시에 지어야한다.
예를 들어 2번(건설 시간 1초), 3번(건설 시간 100초)을 동시에 지을수 있다면 동시에 짓고 그 중에서 건설 시간이 가장 긴 100초를 dp 배열에 저장하면 된다.
점화식
dp[next] = Math.max(dp[next], dp[cur] + buildTime[next]);
/* 현재 next를 건설 하기 전에 지어야하는 건물들 중에 건설시간이 가장 긴
건물을 더 해주는 과정. */
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
StringBuilder ans = new StringBuilder();
for (int k = 0; k < T; k++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] buildTime = new int[N + 1];
int[] indegree = new int[N + 1];
int[] dis = new int[N + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= N; i++) {
buildTime[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(a).add(b);
indegree[b]++;
}
int W = Integer.parseInt(br.readLine());
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
dis[i] = buildTime[i];
}
}
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next: graph.get(cur)) {
dis[next] = Math.max(dis[next], dis[cur] + buildTime[next]);
if(--indegree[next] == 0) {
queue.offer(next);
}
}
}
ans.append(dis[W]);
ans.append("\n");
}
System.out.println(ans);
}
}
Author And Source
이 문제에 관하여(백준 1005번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@oppurity12/백준-1005번
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
dp[next] = Math.max(dp[next], dp[cur] + buildTime[next]);
/* 현재 next를 건설 하기 전에 지어야하는 건물들 중에 건설시간이 가장 긴
건물을 더 해주는 과정. */
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
StringBuilder ans = new StringBuilder();
for (int k = 0; k < T; k++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] buildTime = new int[N + 1];
int[] indegree = new int[N + 1];
int[] dis = new int[N + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 1; i <= N; i++) {
buildTime[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(a).add(b);
indegree[b]++;
}
int W = Integer.parseInt(br.readLine());
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
queue.offer(i);
dis[i] = buildTime[i];
}
}
while (!queue.isEmpty()) {
int cur = queue.poll();
for (int next: graph.get(cur)) {
dis[next] = Math.max(dis[next], dis[cur] + buildTime[next]);
if(--indegree[next] == 0) {
queue.offer(next);
}
}
}
ans.append(dis[W]);
ans.append("\n");
}
System.out.println(ans);
}
}
Author And Source
이 문제에 관하여(백준 1005번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@oppurity12/백준-1005번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)