[BOJ / 구현] 19535 ㄷㄷㄷㅈ

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

19535번: ㄷㄷㄷㅈ

 

19535 ㄷㄷㄷㅈ

알고리즘 : 구현

아이디어성 구현 문제입니다. ㄷ인 트리는 두 인접한 간선 사이의 (자식-1)을 곱하면 2ㄷ가 나와 2를 나눠주면 얻을 수 있고, ㅈ인 트리는 해당 정점이 자식이 n개일 경우 n! / (n-3)!3! 이므로 n(n-1)(n-2) / 6으로 구할 수 있습니다. 최대 자식이 30만일 경우 30만*30만*30만 / 6이 나올 수 있으므로 계산에 들어가는 정수형은 long long int로 선언해주어야 합니다. 

 

 

 

< CODE >

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MAX 300005

vector<int> inj[MAX];
string dudu = "DUDUDUNGA";

long long int d = 0;
long long int g = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		int v1 = 2, v2 = i+1;

		cin >> v1 >> v2;

		inj[v1].push_back(v2);
		inj[v2].push_back(v1);
	}
	
	for (int i = 1; i <= n; i++)
	{
		long long int _size = inj[i].size();

		g += _size * (_size - 1) * (_size - 2) / 6;

		for (int j = 0; j < _size; j++)
		{
			int to = inj[i][j];

			d += (_size - 1) * (inj[to].size() - 1);
		}
	}

	d >>= 1;

	if (d > g * 3)
		cout << "D\n";
	else if (d < g * 3)
		cout << "G\n";
	else
		cout << dudu << '\n';

	return 0;
}

시간 : 148ms

 

태그 : #BOJ ㄷㄷㄷㅈ #백준 ㄷㄷㄷㅈ #19535 ㄷㄷㄷㅈ #UCPC ㄷㄷㄷㅈ