[c++] BOJ 19535 :: ㄷㄷㄷㅈ

난이도 : 골드 3

 

문제

ㄷㄷㄷㅈ 문제 바로가기

정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고 하자.

이제, 동현이는 세상의 모든 트리를 다음과 같은 세 종류로 나누었다.

• D-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 많은 트리
• G-트리 : ‘ㄷ’이 ‘ㅈ’의 3배보다 적은 트리
• DUDUDUNGA-트리 : ‘ㄷ’이 ‘ㅈ’의 정확히 3배만큼 있는 트리

신이 난 동현이는 트리만 보이면 그 트리에 있는 ‘ㄷ’과 ‘ㅈ’이 몇 개인지 세고 다니기 시작했다. 하지만 곧 정점이 30만 개나 있는 트리가 동현이 앞에 나타났고, 동현이는 그만 정신을 잃고 말았다. 동현이를 대신해 주어진 트리가 D-트리인지 G-트리인지 아니면 DUDUDUNGA-트리인지 알려주자!

 

풀이

• ㅈ은 간선이 3개 이상인 노드에서 나타난다.
  • 간선이 n개 일 때, 3개만 고르는 경우의 수만큼 ㅈ가 나타나므로
  • ㅈ는 nC3인 (n)(n-1)(n-3)/6 개 만큼 나올 수 있다.

• ㄷ은 간선이 2개인 노드가 2개 연속해서 등장하고 각각 연결된 다른 노드가 있으면 나타난다.
  • ?-n-m-? 구조일 때, ㄷ은 (n-1)*(m-1) 개 만큼 나올 수 있다.

 

코드

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

using namespace std;

long long int dNum = 0; long long int gNum = 0;
vector<int> visited(300005, 0);

void calTree(vector<vector<int>>& tree, int node, int currD) {
    visited[node] = 1;
    int linkSize = tree[node].size();
    if (linkSize >= 3) {
        gNum += linkSize * (linkSize - 1) * (linkSize - 2) / 6; // 이부분을 생각 못해씀!
    }
    if (linkSize >= 2) {
        if (currD != 0) {
            dNum += currD * (linkSize - 1);
        }
    }
    currD = linkSize - 1;
    for (int i = 0; i < linkSize; i++) {
        int nextNode = tree[node][i];
        if (visited[nextNode] != 0)
            continue;
        calTree(tree, nextNode, currD);
    }
}

string returnTreeType() {
    if (dNum > gNum * 3) {
        return "D";
    }
    else if (dNum < gNum * 3) {
        return "G";
    }
    else {
        return "DUDUDUNGA";
    }
}

int main() {
    // ㅈ => 연결된 노드가 n개인 노드에서 ㅈ (n)(n-1)(n-3)/6개
    // ㄷ => 연결된 노드가 2개 이상인 노드 옆에 또 2개 이상이 노드가 있을 때 => 각자에게 연결된 노드 수의 곱만큼 ㄷ이 나옴
    // n : 10^6

    int N; cin >> N;
    vector<vector<int>> tree(N + 1, vector<int>()); // 해당 노드와 연결된 노드의 idx
    for (int i = 0; i < N-1; i++) {
        int s, e; cin >> s >> e;
        tree[s].push_back(e);
        tree[e].push_back(s);
    }

    calTree(tree, 1, 0);
    cout << returnTreeType();
}

 

 

결과

아이디	메모리	시간	코드 길이
gmldms784	38196	460	1317