[BOJ/백준] 19535 ㄷㄷㄷㅈ

import sys
from itertools import combinations
import math
def input():
    return sys.stdin.readline().rstrip()
 
 
 
N = int(input())
 
graph = [[] for _ in range(N+1)]
 
 
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
d_cnt = 0
g_cnt = 0
 
 
for i in range(1,N+1):
    if len(graph[i])>=3:
        k = len(graph[i])
        cnt = math.factorial(k)/(math.factorial(3)*math.factorial(k-3))
        g_cnt += cnt
    if len(graph[i])>=2:
        for next_node in graph[i]:
            if len(graph[next_node])>=2:
                a = len(graph[i]) - 1
                b = len(graph[next_node]) - 1
                d_cnt += (a*b)
 
d_cnt//=2
 
if d_cnt > g_cnt*3:
    print('D')
elif d_cnt < g_cnt*3:
    print('G')
else:
    print('DUDUDUNGA')

ㅈ 을 그리는 방법은 해당 노드를 기준으로 자식노드가 3개이상이면 구할수 있따. 그러므로 자식노드 중 3개를 고르는 경우의 수를 더해주면 된다.

 

 

ㄷ을 그리는 방법은 다음과 같다. 서로 연결된 두 노드의 자식노드가 2개이상이어야할때이다.

 

왜냐하면 서로 연결이 되어 있으므로, 하나는 빼고 서로 다른 노드들의 개수를 곱해주면 된다.

 

 

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def nC3(n):
    return (n*(n-1)*(n-2))//6
 
N = int(input())
 
graph_node_cnt = [0 for _ in range(N+1)]
edge_list = []
for _ in range(N-1):
    x,y = map(int,input().split())
    graph_node_cnt[x] += 1
    graph_node_cnt[y] += 1
    edge_list.append((x,y))
 
g_cnt = 0
d_cnt = 0
for node in range(1,N+1):
    if graph_node_cnt[node] >=3:
        g_cnt += nC3(graph_node_cnt[node])
 
for x,y in edge_list:
    if graph_node_cnt[x]>=2 and graph_node_cnt[y]>=2:
        d_cnt += (graph_node_cnt[x]-1)*(graph_node_cnt[y]-1)
 
 
if d_cnt>3*g_cnt:
    print('D')
elif d_cnt < 3*g_cnt:
    print('G')
else:
    print('DUDUDUNGA')

이건 팩토리얼 대신 사용한 것이다.