프로그램 명: koi_toy
제한시간: 1 초
우리는 장난감을 여러 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본
부품과 그 기본 부품들을 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을
사용하여 조립할 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을
이용하여 만들어 지는 부품이다.
예를 들어 보자.
- 기본 부품으로서 1,2,3,4 가 있다.
- 중간 부품 5 는 2 개의 기본 부품 1 과 2개의 기본 부품 2로 만들어 진다.
- 중간 부품 6 은 2 개의 중간 부품 5, 3 개의 기본 부품 3 과 4개의 기본 부품 4로 만들어진다.
- 마지막으로 장난감 완제품 7 은 2 개의 중간 부품 5, 3 개의 중간 부품 6 과 5 개의 기본 부품 4로 만들어진다.
이런 경우에 장안감 완제품 7 을 만드는데 필요한 기본 부품의 개수는 1 번 16 개, 2 번 16
개, 3 번 9 개, 4 번 17 개이다.
이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때
하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는
프로그램을 작성하시오.
제한 시간은 1 초이다.
입력 형식
입력의
- 첫째 줄에는 정수 N(3 <= N <= 100)이 주어지는데, 1 부터 N-1 까지는 기본 부품이나 중간 부품의 번호를 나타내고 N
은 완 제품의 번호를 나타낸다.
- 그 다음 줄에는 정수 M(3 <= M <= 100)이 주어지고
- 다음 M 개의 줄에는 어떤 부품을 완성하는데 필요한 부품들 간의 관계가
3 개의 정수 X,Y,K 로 주어진다. 이 뜻은 중간 부품이나 완제품 X 를 만드는데 필요한
중간 부품 혹은 기본 부품 Y 가 K 개 필요하다는 뜻이다.
출력 형식
- 첫 줄에 기본 부품의 수를 출력하고
- 다을 줄 부터 하나의 완제품을 조립하는데 필요한 기본 부품의
수를 한 줄에 하나씩 출력하되(중간 부품은 출력하지 않음), 반드시 기본 부품의 번호가
작은 것부터 큰 순서가 되도록한다. 각 줄에는 기본 부품의 번호와 소요 개수를 출력한다.
입력과 출력의 예
입력
7
8
5 1 2
5 2 2
7 5 2
6 5 2
6 3 3
6 4 4
7 6 3
7 4 5
출력
4
1 16
2 16
3 9
4 17
출처:koi 중등 기출
[질/답]
[제출 현황]
[푼 후(4)]