[백준/C++] 19535. ㄷㄷㄷㅈ

문제

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

풀이

ㄷ 트리 : (n과 연결된 노드(a 제외)) - (n) - (n과 연결된 노드(a)) - (a와 연결된 노드(n 제외))

따라서 경우의 수는 모든 노드(n)에 대해서, 

n과 연결된 노드가 x개라고 하고, 

n과 연결된 어떤 노드 a와 연결된 노드가 y개라고 하면, 

(x-1) * (y-1) 의 합으로 구할 수 있다. 

 

* 중복을 막기 위해, n이 a보다 노드번호가 큰 경우만 셈

 

ㅈ 트리 : (n) - (n과 연결된 노드 3개)

따라서 경우의 수는,

연결된 노드의 개수 a가 3 이상인 노드 n에 대해서 aC3 의 총 합을 구하면 된다. 

코드

#include <iostream>
#include <vector>

using namespace std;

int N;

vector<int> tree[300003];

long long count_d = 0;
long long count_g = 0;

void find_g() {
	// 자식이 3개 이상인 노드에서, 자식수가 a라고 했을 때, aC3 개수 세기 
	for (int n = 1;n <= N;n++) {
		int cnt = tree[n].size(); // 자식 개수
		if (cnt >=3) 
			count_g += (cnt*(cnt - 1)*(cnt - 2)) / 6;
	}
}
// n의 자식or부모 - n - tree[n][i] - tree[n][i]의 자식or부모 
// n의 자식or부모에서 tree[n][i]는 빼줘야 하므로 -1 (1)
// tree[n][i]의 자식or부모에서 n은 빼줘야 하므로 -1 (2)
// 경우의수 계산 : (1)*(2)
void find_d() { 
	for (int n = 1;n <= N;n++) {
		if (tree[n].size() < 2) continue;
		for (int i = 0;i < tree[n].size();i++) {
			if (tree[n][i] < n) continue;
			if (tree[tree[n][i]].size() < 2) continue;
			count_d += ((tree[n].size()-1)*(tree[tree[n][i]].size()-1));
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i = 1;i < N;i++) { // 간선 N-1개 입력받기 
		int u, v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);	
	}
	
	find_d();
	find_g();
	//cout << count_d << " " << count_g << endl;
	if (count_d > count_g * 3) cout << "D";
	else if (count_d == count_g * 3) cout << "DUDUDUNGA";
	else cout << "G";

	return 0;
}

결과