You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이고, 중간 부품은 또 다른 중간 부품이나 기본 부품으로 만들어진다.
완제품과 그에 필요한 부품들 사이의 관계가 주어졌을 때 완제품을 조립하기 위해 필요한 기본 부품의 종류별 개수를 계산하라
1~N개의 부품 N(3 ≤ N ≤ 100). N은 완제품.
M개의 부품 관계 M(3 ≤ M ≤ 100) : X, Y, K -> X를 만드는데 중간 혹은 기본 부품 Y가 K개 필요하다.
두 중간 부품이 서로를 필요로 하는 경우는 없다.
아이디어
2시간 걸려서 겨우 해결한 문제.. 풀고 나면 진짜 아무것도 아닌데 왜 이렇게 오래 걸리는지...
부품별로 만드는데 필요한 부품 번호와 개수를 그래프로 나타낸다.
기본 부품부터 시작해 위상정렬을 하면서 필요한 기본 부품 개수 계산하기
이 때 이전 부품이 cnt개 필요하다면 이전 부품의 기본 부품 정보들에 cnt 곱한 값을 적용하면 된다.
시간 복잡도
위상정렬하는데에는 O(V+E)의 시간이 걸린다. 그런데 간선마다 필요한 부품 수를 갱신하는 과정에서 N만큼의 시간이 더 걸린다. 따라서 O(V+E*N)이다. 정점의 최대 수는 100개이고, 간선의 수도 100개이고, N의 최댓값도 100이므로 시간 안에 풀이가 가능하다.
구현
importjava.io.*;
importjava.util.*;
publicclassMain {
staticBufferedWriterbw = newBufferedWriter(newOutputStreamWriter(System.out));
staticBufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));;
staticStringTokenizerst;
staticintN, M;
staticArrayList<Part>[] adj;
staticint[] indeg;
staticint[][] cnt;
staticclassPart {
intnum, cnt;
publicPart(intnum, intcnt) {
this.num = num;
this.cnt = cnt;
}
}
publicstaticvoidinit() throwsIOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
adj = newArrayList[N + 1];
for (inti = 1; i <= N; i++) adj[i] = newArrayList<>();
cnt = newint[N + 1][N + 1];
indeg = newint[N + 1];
for (inti = 1; i <= M; i++) {
st = newStringTokenizer(br.readLine());
intnum = Integer.parseInt(st.nextToken());
intblock = Integer.parseInt(st.nextToken());
intcnt = Integer.parseInt(st.nextToken());
adj[block].add(newPart(num, cnt));
indeg[num]++;
}
}
privatestaticvoidpro() throwsIOException {
tpSort();
for (inti = 1; i <= N; i++) {
if (cnt[N][i] > 0)
bw.write(i + " " + cnt[N][i] + "\n");
}
}
privatestaticvoidtpSort() throwsIOException {
Queue<Integer> que = newLinkedList<>();
for (inti = 1; i <= N; i++) {
if (indeg[i] == 0) {
que.add(i);
cnt[i][i] = 1;
}
}
while (!que.isEmpty()) {
intx = que.poll();
for (Party : adj[x]) {
indeg[y.num]--;
for (inti = 1; i <= N; i++) {
cnt[y.num][i] += cnt[x][i] * y.cnt;
}
if (indeg[y.num] == 0) que.add(y.num);
}
}
}
publicstaticvoidmain(String[] args) throwsException {
init();
pro();
bw.close();
}
}
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/2637
문제 조건
기본 부품과 그 기본 부품으로 만든 중간 부품이 있다.
기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이고, 중간 부품은 또 다른 중간 부품이나 기본 부품으로 만들어진다.
완제품과 그에 필요한 부품들 사이의 관계가 주어졌을 때 완제품을 조립하기 위해 필요한 기본 부품의 종류별 개수를 계산하라
1~N개의 부품 N(3 ≤ N ≤ 100). N은 완제품.
M개의 부품 관계 M(3 ≤ M ≤ 100) : X, Y, K -> X를 만드는데 중간 혹은 기본 부품 Y가 K개 필요하다.
두 중간 부품이 서로를 필요로 하는 경우는 없다.
아이디어
2시간 걸려서 겨우 해결한 문제.. 풀고 나면 진짜 아무것도 아닌데 왜 이렇게 오래 걸리는지...
시간 복잡도
위상정렬하는데에는 O(V+E)의 시간이 걸린다. 그런데 간선마다 필요한 부품 수를 갱신하는 과정에서 N만큼의 시간이 더 걸린다. 따라서 O(V+E*N)이다. 정점의 최대 수는 100개이고, 간선의 수도 100개이고, N의 최댓값도 100이므로 시간 안에 풀이가 가능하다.
구현
All reactions