이번 문제에서는 무한한 깊이를 가질 수 있는 트리가 주어집니다. 노드가 가질 수 있는 자식의 수를 저장하는 변수 child, 경로에 부여되는 가중치를 나타내는 변수 weight, 그리고 목표 총 가중치(X)를 저장하는 변수 path가 함께 제공됩니다. 우리의 과제는 총 가중치가 정확히 X와 같으면서, 가중치 M을 가진 간선을 적어도 하나 이상 포함하는 경로의 개수를 계산하는 것입니다.
예시
입력 - int child = 4, weight = 4, path = 4;
출력 - 총 가중치가 정확히 X이고 가중치 M인 간선을 하나 이상 포함하는 경로의 수: 1
설명 - 자식이 4개인 노드가 4개의 경로로 연결되어 있으며, 각 경로에는 가중치 4가 부여되어 있습니다. 가중치의 합이 4가 되면서 가중치 4짜리 간선을 포함하는 경로는 (4) 하나뿐이므로 개수는 1입니다.
입력 - int child = 3, weight = 2, path = 4;
출력 - 총 가중치가 정확히 X이고 가중치 M인 간선을 하나 이상 포함하는 경로의 수: 4
설명 - 자식이 3개인 노드가 4개의 경로로 연결되어 있으며, 각 경로에는 가중치 2가 부여되어 있습니다. 가중치의 합이 4가 되면서 가중치 2짜리 간선을 포함하는 경로는 (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2)의 네 가지이므로 개수는 4입니다.
프로그램에서 사용된 접근 방식
이 문제는 메모이제이션(memoization)을 활용한 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 재귀 함수의 두 번째 매개변수 i는 지금까지 탐색한 경로에 가중치 M인 간선이 포함되었는지 여부를 나타내는 플래그 역할을 하며, 경로의 합이 0에 도달했을 때 이 플래그 값을 반환함으로써 조건을 만족하는 경우만 카운트하게 됩니다.
- 자식 수, 목표 가중치(M), 경로의 총합(X)을 각각 child, weight, path 변수에 입력받습니다.
- 주어진 크기의 2차원 배열을 선언합니다.
- i를 0부터 배열 크기까지 반복하는 FOR 루프 안에서, j를 0부터 2 미만까지 반복하며 arr[i][j]를 -1로 설정합니다. (-1은 아직 계산되지 않은 상태를 의미합니다.)
- path, 0, weight, child, arr을 인수로 전달하여 total_weight() 함수를 호출합니다.
- 함수 내부에서 다음을 수행합니다.
- 결과를 저장할 임시 변수 count를 선언합니다.
- path가 0보다 작으면 0을 반환합니다.
- path가 0이면 i를 반환합니다. (가중치 M인 간선을 포함했다면 1, 아니면 0)
- arr[path][i]가 -1이 아니라면 이미 계산된 값이므로 해당 값을 그대로 반환합니다.
- j를 1부터 child까지 반복하는 FOR 루프를 실행합니다. 루프 내부에서 j가 weight와 같으면 count에 total_weight(path - j, 1, weight, child, arr)의 재귀 호출 결과를 더합니다.
- 그렇지 않으면 count에 total_weight(path - j, i, weight, child, arr)의 재귀 호출 결과를 더합니다.
- 계산이 끝나면 arr[path][i]를 count로 설정합니다.
- arr[path][i]를 반환합니다.
- 최종 결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define size 4
#define col 4
int total_weight(int path, int i, int weight, int child, int arr[size + 1][col]) {
int count = 0;
if (path < 0) {
return 0;
}
if (path == 0) {
return i;
}
if (arr[path][i] != -1) {
return arr[path][i];
}
for (int j = 1; j <= child; j++) {
if (j == weight) {
count += total_weight(path - j, 1, weight, child, arr);
} else {
count += total_weight(path - j, i, weight, child, arr);
}
}
arr[path][i] = count;
return arr[path][i];
}
int main() {
int child = 4, weight = 4, path = 4;
int arr[size + 1][col];
for (int i = 0; i <= size; i++) {
for (int j = 0; j < 2; j++) {
arr[i][j] = -1;
}
}
cout << "Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: " << total_weight(path, 0, weight, child, arr);
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력
Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1