[ baekjoon ] ㄷㄷㄷㅈ 19535번 ( python )

문제

백준 19535 ㄷㄷㄷㅈ 풀이 ( 파이썬 )

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

19535번: ㄷㄷㄷㅈ

 

풀이

일단 ㄷ을 구할 경우와 ㅈ을 구할 경우를 나눴다.

ㅈ를 구하는 방법은 노드 하나를 기준으로 연결된 노드가 3개 이상일 때 이 연결된 노드중 3개를 선택하면 된다.

degree[i] * (degree[i] - 1) * (degree[i] - 2) / 6 if degree[i] >= 3 else 0

위의 식은 nC3 일때의 식을 풀어 쓴것이다. (degree[i]가 3이상일 때는 풀어쓴 식 사용, 미만일 떄는 0)

 

ㄷ은 연결된 선을 기준(지금은 빨간 선)으로 연결된 두 노드(초록 노드)에 각각 연결된 점들을 곱해주면 ㄷ의 개수가 된다.

((degree[dot1] - 1) * (degree[dot2] - 1))

각 노드에 -1을 해준 이유는 초록 서로 초록 노드인 경우는 지우기 위함이다.

 

import sys

input = sys.stdin.readline

n = int(input())

lines = []
degree = [0] * (n + 1)

for i in range(n-1):
    s, e = map(int, input().split())
    lines.append((s, e))

    degree[s] += 1
    degree[e] += 1

d_cnt = 0
j_cnt = 0

# ㅈ 개수 구하기
for i in range(1, n + 1):
    j_cnt += degree[i] * (degree[i] - 1) * (degree[i] - 2) / 6 if degree[i] >= 3 else 0

for line in lines:
    dot1, dot2 = line
    d_cnt += ((degree[dot1] - 1) * (degree[dot2] - 1))

if d_cnt > 3 * j_cnt:
    print("D")
elif d_cnt < 3 * j_cnt:
    print("G")
else:
    print("DUDUDUNGA")