백준 2637번 장난감 조립

문제

https://www.acmicpc.net/problem/2637

기본 부품과 중간 부품을 사용해 최종 완제품을 만드는 것이 문제의 컨셉입니다.
중간 부품도 기본 부품으로 이루어져있는데, 이때 완제품을 만들기 위한 모든 기본 부품의 개수를 구하는 것이 문제에서 바라는 데이터입니다.
완제품을 만들기 위해 다른 부품들이 선행되어야 하고, 또 그 부품들도 다른 부품들이 준비되어있어야 하기 때문에 위상 정렬을 사용할 수 있는 문제입니다.

"두 중간 부품이 서로를 필요로 하는 경우가 없다"는 말로 미루어 봤을때 다행히 사이클은 발생하지 않는다는걸 알 수 있지만, 총 100개의 부품들이 관계가 얽히다보면 특정 부품의 기본 부품을 하나하나 다 구하다가 시간 초과가 날 가능성이 있습니다.
다행히 특정 중간부품을 구성하는 부품들은 변할 가능성이 없기 때문에, dp를 이용해 구성하는 값을 캐싱하면 중복되는 값을 다시 계산하지 않아 더 좋은 퍼포먼스를 낼 수 있습니다.

1차 시도

#include <vector>
#include <cstdio>

using namespace std;

int n, m, a[101][5], dp[101];
vector<pair<int, int>> l[10001];

int f(int x, int p, int b) {
    if (x < 5) return !!(a[p][x] += b);
    if (dp[x]) return dp[x];
    for (auto [v, w]: l[x]) {
        dp[x] += f(v, x, w) * w;
        for (int i = 1; i <= 4; i++) a[x][i] += a[v][i] * w;
    }
    return dp[x];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, b, c, d; i <= m; i++) {
        scanf("%d %d %d", &b, &c, &d);
        l[b].emplace_back(c, d);
    }
    f(n, 0, 0);
    for (int i = 1; i <= 4; i++) {
        printf("%d %d\n", i, a[n][i]);
    }
}

7%에서 틀렸습니다를 받았는데요.. 문제를 꼼꼼히 읽어보지 않아서 기본부품은 무조건 1~4일거라는 착각을 해버렸습니다. ㅠㅠ
위상 정렬의 특성을 이용해 진출차수가 0인 부품들을 기본 부품으로 판단하도록 재귀함수의 종료 조건을 다시 설정했습니다.

2차 시도

#include <vector>
#include <cstdio>

using namespace std;

int n, m, a[101][101], dp[101], e[101];
vector<pair<int, int>> l[101];

int f(int x, int p, int b) {
    if (!e[x]) return !!(a[p][x] += b);
    if (dp[x]) return dp[x];
    for (auto [v, w]: l[x]) {
        dp[x] += f(v, x, w) * w;
        for (int i = 1; i <= n; i++) a[x][i] += a[v][i] * w;
    }
    return dp[x];
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, b, c, d; i <= m; i++) {
        scanf("%d %d %d", &b, &c, &d);
        e[b]++;
        l[b].emplace_back(c, d);
    }
    f(n, 0, 0);
    for (int i = 1; i <= n; i++) {
        if (!e[i]) printf("%d %d\n", i, a[n][i]);
    }
}

조금 더 좋은 코드를 작성할 수 있었지만 회사 점심시간이 1분밖에 남지 않아서 조금만 수정하고 제출한 코드입니다. 1272kb에 0ms로 맞았습니다를 받았습니다.
e라는 배열로 진출차수를 기록 후 종료 조건도 e[i]가 0일때만 기본 부품으로 인식해서 리턴해주었습니다. !!를 사용하면 0 아니면 1로 인식하기 때문에 "최종적으로 필요한 기본부품의 갯수"는 더하더라도 그냥 필요한 기본부품의 개수 1개를 잘 반환해주기 때문에 괜찮습니다. 사실 한줄로 반환하려는 욕심이 더 커서 저런 코드를 작성한게 더 큽니다.. ㅎㅎ;

아름다운 재귀함수를 짤 때는 항상 기분이 좋네요 :) 요즘 회사 업무 관련된 공부를 하느라 알고리즘 풀 시간이 많이 없었는데 매우~ 재밌었습니다. 생각지도 못하게 1점이 올라서 이제 1910점이네요. 읽어주셔서 감사합니다.