JUNGOL 실력키우기 1021 : 장난감조립

우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.

 

예를 들어보자. 기본 부품으로서 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개 이다.

 

이와 같이 어떤 장난감 완제품과 그에 필요한 부품들 사이의 관계가 주어져 있을 때 하나의 장난감 완제품을 조립하기 위하여 필요한 기본 부품의 종류별 개수를 계산하는 프로그램을 작성하시오.

 

입력 파일의 첫째 줄에는 정수 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

1 16 2 16 3 9 4 17

---

이번 문제는 생각을 좀 해야 풀수 있는 문제였네요.

먼저 데이터 형식을 보면 원하는 파트, 필요한 파트, 필요한 개수로 되어있으므로 그런 구조체를 하나 만들어줍니다.

그리고 문제를 잘 읽어보면 결국 마지막 파트를 만드는데 중간 과정이 필요한 것이므로 전체에 대해서 연산을 할 필요가 없이 원하는 파트가 마지막 파트인 경우에만 즉, 완성품인 경우에만 연산을 해 주면 됩니다.

원하는 파트가 주어진 과정에 없다면 해당 파트는 기본 파트이므로 해당 위치에 개수를 저장해주면 됩니다.

이때, 상위 파트에서 내려오면서 배수를 해 주면 됩니다.

가령 7번 파트를 만들 때, 6번이 3개 필요한데 6번은 5번이 2개 필요합니다. 즉 5번에서 필요한 1번 2개, 2번 2개는 필요한 5번의 개수를 만들기 위해 각각 4개씩이 필요하고 6번을 만들기 위해 6번이 3개 필요하므로 12개가 됩니다. 즉,  3 * 2가 배수가 되는 것입니다.

이 부분을 잘 생각하시면 풀 수 있을 것 같습니다.

#include <iostream>
#include <vector>
 
using namespace std;
 
// 입력받을 데이터 형식대로 새로운 구조체를 만든다.
struct MakingInfo {
    int wantPart;
    int needPart;
    int needCount;
};
 
// 개수 처리 함수, 기본 배수는 1로 처리한다.
void FindTotalCounts(vector<MakingInfo>& data, int index, int mul = 1);
 
// 필요한 개수를 저장할 배열, 입력 가능 개수가 100까지이므로 101로 지정
int totalCounts[101];
 
int main()
{
    int n, cnt;
    cin >> n >> cnt;
 
    vector<MakingInfo> data;
    while (cnt > 0)
    {
        MakingInfo newData;
        cin >> newData.wantPart
            >> newData.needPart
            >> newData.needCount;
        data.push_back(newData);
        cnt--;
    }
 
    // 원하는 파트가 최종 결과물인 경우에만 처리한다.
    for (int i = 0; i < data.size(); ++i)
    {
        if (data[i].wantPart == n)
        {
            FindTotalCounts(data, i);
        }
    }
 
    // 개수가 0보다 큰 경우에만 출력한다.
    for (int i = 1; i < 101; ++i)
    {
        if (totalCounts[i] > 0)
        {
            printf("%d %d\n", i, totalCounts[i]);
        }
    }
}
 
void FindTotalCounts(vector<MakingInfo>& data, int index, int mul)
{
    if (index < 0) return;
 
    bool basicPart{ true };
    for (int i = 0; i < data.size(); ++i)
    {
        // 만약 중간 과정 리스트에 원하는 파트가 있다면 기본 파트가 아니다.
        // 그러므로 재귀를 통해 기본 파트의 개수를 구한다.
        // 이때 원하는 개수를 배수로 추가한다.
        if (data[i].wantPart == data[index].needPart)
        {
            basicPart = false;
            FindTotalCounts(data, i, data[index].needCount * mul);
        }
    }
 
    // 기본 파트인 경우에만 개수를 더한다.
    if (basicPart)
    {
        totalCounts[data[index].needPart] += data[index].needCount * mul;
    }
}

JUNGOL) 문제은행) 실력키우기) 장난감조립