[1일 1알고] 모두 0으로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/76503

프로그래머스

중요한 것은 주어진 노드들이 트리로서 이어져있다는 것입니다.

기본적으로는 주어진 수 a의 합이 0이 아니라면 애초에 성립할 수 없다는 뜻입니다.

 

따라서 이 경우를 예외처리하고 어제 풀었던 등대문제 처럼 tree DP처럼 풀면 되겠네요

https://basaeng.tistory.com/165

[1일 1알고] 2차원 동전 뒤집기

 

끌어올리면서 말단노드와의 차이를 누적시키면 됩니다. 결론적으로는 루트 노드에서 취합하여 0을 만들어야합니다.

 

#include <string>
#include <vector>

using namespace std;

int n = 0;
vector<vector<int>> roads;
long long answer = 0;

void dfs(int cur, int parent, vector<long long>& a)
{
    for (auto next : roads[cur])
    {
        if (next == parent)
            continue;

        dfs(next, cur, a);
    }

    if (parent == -1)
        return;

    a[parent] += a[cur];
    answer += llabs(a[cur]);
    a[cur] = 0;
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    answer = 0;

    n = a.size();

    long long total = 0;
    for (int elem : a)
    {
        total += elem;
    }

    if (total != 0)
        return -1;

    roads.assign(n, vector<int>());

    for (auto edge : edges)
    {
        roads[edge[0]].push_back(edge[1]);
        roads[edge[1]].push_back(edge[0]);
    }

    vector<long long> weights(a.begin(), a.end());

    dfs(0, -1, weights);

    return answer;
}

어제의 등대 문제보다는 훨씬 간단합니다.

 

다만 문제는 누적되는 값이 int의 범위를 넘을 수 있기 때문에 이를 신경써야겠네요

물론 몇개의 예시에서 제가 틀려서 하는 말입니다.