[C++] 백준 2637: 장난감 조립

문제 이해

- 완제품: 기본 부품 + 중간 부품

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 128MB

 

<입력>

- N: 완제품의 번호 (3 ~ 100, 10^2)

- M: 관계의 개수 (3 ~ 100, 10^2)

- 관계(완제품, 중간 부품 or 기본 부품, 필요한 개수)

 

<출력>

- 하나의 완제품을 만들기 위하여 필요한 기본 부품의 종류별 개수

 

 

문제 풀이

기본 부품과 중간 부품을 조합하여 완제품을 만든다는 점에서 선행 관계가 있다고 볼 수 있다.

즉 위상 정렬을 사용하여 푸는 문제이다.

 

 

개수를 구해야 하므로 DP를 사용해야 할 거 같은데 시간을 구하는 여러 문제들과 달리 개수를 구하는 문제였다.

 

문제의 입력이 주어지는 것에서 힌트를 얻을 수 있는데,

완제품에서 시작하여 위상정렬을 시작하면 문제를 쉽게 풀 수 있다. 

 

 

<주의해야 할 점>

1. dp[n] = 1로 설정해야 한다.

완제품을 기반으로 개수를 탐색해 나가므로 초기 설정을 반드시 잘해줘야 한다.

dp[n] = 1;

 

2. 기본 부품이 어떤 것인지 찾는 코드가 필요하다.

다양한 방법이 있겠지만 역방향으로 생각했을 때, 기본 부품들은 나가는 간선의 개수가 없는 점을 활용했다.

if(v[now].empty()){
            ans.push_back(now);
        }

 

3. dp에 개수를 더할 때 += 연산자를 활용해야 한다.

개수는 기존의 개수와 더해가야 하므로 주의하자.

dp[next] += dp[now] * num;

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector <pair<int, int>> v[105];
int inDegree[105];
int dp[105];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int a, b, cost;
        cin>>a>>b>>cost;
        v[a].push_back({b, cost});
        inDegree[b]++;
    }

    vector <int> ans;
    queue <int> q;
    q.push(n);
    dp[n] = 1;

    while(!q.empty()){
        int now = q.front();
        q.pop();

        if(v[now].empty()){
            ans.push_back(now);
        }

        int size = v[now].size();
        for(int i = 0; i < size; i++){
            int next = v[now][i].first;
            int num = v[now][i].second;
            inDegree[next]--;
            dp[next] += dp[now] * num;

            if(inDegree[next] == 0){
                q.push(next);
            }
        }
    }

    sort(ans.begin(), ans.end());
    int size = ans.size();
    for(int i = 0; i < size; i++){
        int tmp = ans[i];
        cout<<tmp<<" "<<dp[tmp]<<"\n";
    }
    return 0;
}

정방향으로 생각하여 풀이가 쉽게 나오지 않았는데, 역방향으로 생각해보니 바로 해결되었다.

발상을 유연하게 할 수 있도록 많은 문제를 풀자.