[G4] 백준 25515번 트리 노드 합의 최댓값 C++ 트리, 다이나믹 프로그래밍

리뷰

 

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

int범위를 넘어설땐 꼭 모든 정수형 타입을 확인하자...

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• w : 각 노드의 가중치를 저장할 배열
• dp : 각 노드의 최대 가중치를 저장할 배열
• n : 노드의 개수를 저장할 변수
• edges : 인접 리스트를 저장할 벡터 배열

 

함수

1. dfs

ll dfs(int cn) {
	if (edges[cn].empty()) return w[cn];
	dp[cn] = w[cn];

	for (int nn : edges[cn]) {
		dp[cn] = max(dp[cn], dp[cn] + dfs(nn));
	}

	return dp[cn];
}

 

루트 노드에서 시작해 트리 노드 합의 최댓값을 구하기 위한 함수

 

 

문제풀이

1. n값을 입력 받고, n-1개의 간선 정보를 입력 받아 edges를 초기화한다.
2. n개 노드의 가중치를 각각 입력 받아 w배열을 초기화한다.
3. dfs함수에 루트 번호 0을 매개변수로 전달하여 호출한다. 함수 내부에서 변수 cn에 매개변수를 전달받는다.
4. 기저 조건으로 하위 자식이 없을 경우 w[cn]을 리턴한다.
5. 인접 리스트를 순회하며 변수 nn에 하위 자식의 노드 번호를 저장한다.
6. dp[cn]을 dp[cn]과 dp[cn]+dfs(nn)값 중 더 큰 값으로 저장한다.
7. 인접 리스트 순회를 끝낸 경우 dp[cn]에 저장된 값을 리턴한다.
8. dfs함수의 리턴값을 출력한다.

 

트러블 슈팅

1. 절댓값의 범위가 최대 100억까지 생길 수 있으므로 dp, dfs함수의 자료형을 int가 아닌 long long타입으로 해줘야한다.
2. int->long long으로 자료형을 변경하여 AC를 받았다.

 

참고 사항

1. 노드를 방문하면 해당 노드에 적힌 정수는 무조건 더해야 한다.
2. 같은 노드를 여러 번 방문할 수 있고, 여러 번 방문해도 최초 한 번만 해당 노드에 적혀있는 정수를 더한다.
3. 루트 노드는 항상 방문해야 한다.

 

정답 코드

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;

const int N = 1e5;
int w[N];
ll dp[N];
int n;
vector<int> edges[N];

ll dfs(int cn) {
	if (edges[cn].empty()) return w[cn];
	dp[cn] = w[cn];

	for (int nn : edges[cn]) {
		dp[cn] = max(dp[cn], dp[cn] + dfs(nn));
	}

	return dp[cn];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i < n; ++i) {
		int p, c; cin >> p >> c;
		edges[p].push_back(c);
	}

	for (int i = 0; i < n; ++i) cin >> w[i];

	cout << dfs(0);
}