[백준, BOJ 19535] ㄷㄷㄷㅈ (java)

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

19535번: ㄷㄷㄷㅈ

728x90

---

메모리: 88,744 KB , 시간: 516 ms

사용 알고리즘: 조합론, 수학, 트리

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    /**
     * 처음 문제를 해결할 때,
     * 모든 정점들 중 꼭 하나의 간선으로 이어져있는 정점들이 아니더라도
     * 임의의 정점 4개를 뽑아서
     * 뽑은 정점들 중 하나의 정점에서 다른 정점으로 가기 위한 모든 간선들을 남기는 거라고 해석했다.
     *
     * 그럼 (n개의 정점 중 임의의 정점 4개를 뽑는 경우) - (D-트리 개수) = (G-트리 개수) 라고 생각하고
     * 모든 D-트리 개수나 G-트리 개수를 구하려고 했는데,
     * 시간이 너무 오래 걸릴 것 같아서 다른 풀이를 봤다.
     *
     * 풀이를 보다보니 꼭 하나의 간선으로 바로 연결된 정점들 4개를 고르는 거였다..
     *
     * 문제를 이해하고 보니 D-트리, G-트리 개수 구하는 것은 별로 어렵지 않음.
     * 다만, 자료형 크기를 잘 신경써주어야 함.
     */

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[][] edges = new int[N - 1][2];
        long[] countOfEdges = new long[N + 1];

        int u, v;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());

            edges[i][0] = u;
            edges[i][1] = v;

            countOfEdges[u]++;
            countOfEdges[v]++;
        }

        long countD = 0;
        for (int i = 0; i < N - 1; i++) {
            // i번 엣지로 이어지는 두 정점에 대해 'ㄷ'의 개수 구하기
            // edges[i][0]에 연결되어 있는 정점들 중 하나, edges[i][1]에 연결되어 있는 정점들 중 하나.
            countD += (countOfEdges[edges[i][0]] - 1) * (countOfEdges[edges[i][1]] - 1);
        }

        long countG = 0;
        for (int i = 1; i <= N; i++) {
            // 엣지가 3개 이상인 정점에 대해, 이어진 정점들 중 3개 고르기
            if(countOfEdges[i] >= 3) {
                countG += (countOfEdges[i] * (countOfEdges[i] - 1) * (countOfEdges[i] - 2)) / 6;
            }
        }

        if(countD > 3 * countG) System.out.println("D");
        else if(countD < 3 * countG) System.out.println("G");
        else System.out.println("DUDUDUNGA");
    }
}