[문제해결기법] Ordered Tree 완성하기

#include <iostream> #include <fstream> #include <vector> using namespace std; int sum_sub; vector<vector<int>> main_cache = vector<vector<int>>(10001, vector<int>(10001, 0)); //cache : x => 그룹을 지을 노드의 수, y => 나눠야하는 그룹의 개수 //group_count : 나눠야하는 그룹의 개수 //pre_node_count : 그룹을 지을 노드의 수 //pre_group : 현재 나눈 그룹의 수 int main_tree(int group_count, int pre_node_count, int pre_group) { // 현재 노드가 0이고 모든 그룹을 짝지었다면 (모든 그룹을 짝지은후 한번더 DP를 돌림) 현재 그룹이 모든 그룹의 수보다 크다 // 그렇다면 1개의 경우의수가 나옴 if (pre_node_count == 0 && pre_group > group_count) return 1; // 만약 현재 노드가 0이 아닌데 모든 그룹을 짝지었다면 즉 몇개의 노드를 빼먹고 그룹을 짝지었다면 이건 아니지 if (group_count < pre_group) return 0; //만약 이전에 계산해 놓은 것이라면 int&ret = main_cache[group_count - pre_group + 1][pre_node_count]; if (ret != 0) return ret; //그룹에 아무것도 넣지 않는 것부터 나머지 모두를 넣는 것까지 모두 계산 for (int index = 0; index <= pre_node_count; index++) ret += main_tree(group_count, pre_node_count - index, pre_group + 1); return ret; } //group_count : 나눠야하는 그룹의 개수 //pre_node_count : 그룹을 지을 노드의 수 void sub_tree(int group_count, int pre_node_count, int result) { if (pre_node_count == 0) { sum_sub += result; return; } //이 for문이 한 레벨에 두는 노드의 개수를 조절 for (int index = 1; index <= pre_node_count; index++) sub_tree(index, pre_node_count - index, result*main_tree(group_count, index, 1)); //예를들어 현재 레벨에 1개의 노드를 두었으면 다음 레벨에서는 1개의 그룹을 지으면 가능 => 그러므로 첫번째 매개변수 index //두번째는 나머지 노드의 개수 //세번째는 현재 result } int main() { ifstream fcin; fcin.open("C_input.txt"); int for_count, node_count, deep; fcin >> for_count; while (for_count--) { fcin >> node_count >> deep; vector<int>level = vector<int>(deep + 1); int temp = node_count; for (int j = 0; j <= deep; j++) { fcin >> level[j]; node_count -= level[j]; } int result = 1; sum_sub = 0; // 노드가 정해진 것들 for (int j = 0; j < deep; j++) result *= main_tree(level[j], level[j + 1], 1); // 이제 레벨마다 노드가 정해지 않았다면 마음대로 sub_tree(level[deep], node_count, 1); cout << result*sum_sub << endl; } system("pause"); }

어떻게 풀면 시간을 최대한 빨리 풀수 있을 까 생각했다.

일단 DP로 풀었다.

그리고 grouping을 한다고 생각했다. (각각의 노드가 다른 것이 아니므로)

먼저 노드의 개수가 정해진 것들은 main_tree를 돌렸다

몇개의 그룹을 생성해야하는지 그리고 얼마나 많은 node를 넣을 것인지 그리고 현재의 그룹의 개수는 몇개인지를 돌려보는 함수이다.

몇개의 그룹을 생성해야할까?

바로 윗단계의 노드의 수를 보면 된다.

얼마나 많은 노드를 넣어야할까?

먼저 0부터 시작했다 한개도 넣지 않는 그룹도 있으므로

현재의 그룹개수는 몇개일까?

for문안에서 한 그룹의 노드를 index만큼 빼간다 그럼 이후 다음 그룹으로 넘어가기때문에 for문 안에서 함수를 다시 돌때마다 group을 1씩 더해줘야한다

그렇다면 result가 몇인지 나온다 이는 곱해줘야 한다 왜냐하면 

한 레벨마다의 경우의 수이기 때문에 1레벨에서 2가지 2레벨에서 2가지면 총 만들 수 있는 트리의 모양은 4가지이다.

main_tree 함수의 전체적인 흐름은 아래와 같다.

먼저 한개도 넣지 않는다 그렇게 지어야할 그룹의 개수(이하 group_count)가 초과 될때까지 돈다 

초과되면 0을 return

이후 한개를 넣어본다 만약 총 노드의 수가 2개라면 (그룹을 지어야할 노드의 수 이하 node_count)

아직 아니다 return 0 (나머지 노드 수 (이하 remain_node) 가 0이 아닌데 이미 그룹을 다 지어버렸으면)

이후 2개를 넣어본다 

remain_node가 0이고 그룹을 모두 지었다 즉 return 1을 한다

그럼 2개를 모두 넣어보앗으면 이전 그룹으로 돌아간다

아까 이전 그룹에서 한개도 안 넣어보았으니까 이제 1을 넣어본다

그리고 다음그룹으로 넘어온다

다음그룹에서 한개도 안넣어보면 당연 remain_node가 1이기 때문에 return 0

이와 같은 형식으로 반복한다.

cache

y를 지어야 할 총 그룹의 수 x를 총 노드의 수라고 가정해보자

1개의 그룹을 지어야 할때 총 노드가 1개라면 

위 사진 중 2번째 경우에서 2번째에 해당한다고 할 수있다.

즉 이미 이전 노드에서 1개를 썼고 그러므로 현재 노드는 1개 그리고 우리가 채워야하는 나머지 그룹도 1개 이므로

1개의 그룹을 지어야할때 총 노드가 2개라면 

첫번째 경우에 해당한다고 할 수 있다

이미 전 그룹에서는 1개의 노드도 사용하지 않았으므로 2개의 노드가 남았고 남은 그룹의 개수는 1개이므로 

여기서 나온 결과값이 저장된다.

그렇다면 나머지 노드로 마음대로 트리를 생성해야하는데 이것은 어떻게 할 수 있을 까?

cache를 사용하기로 결정했다.

즉 남은 노드는 단지 레벨당 노드의 수만 정해져있지않을뿐이다

따라서 개수만 정해주기만 하면 main_tree함수를 이용해서 결과값을 구할 수 있다.

무조건 레벨당 1개의 노드는 있어야 하므로 index는 1부터 시작한다

1개씩 배분하며 main_tree를 돌려 값을 곱한다.

만약 모든 노드를 사용하였다면 1가지의 경우의수가 나왔다 sum에 더해주자

다시 돌려본다 이번엔 마지막 노드를 1개 더 주자

이렇게 계속 sub_tree를 돌린다

마지막으로 main_tree와 sub_tree에서 나온 값을 곱해주면 답이 나온다.