λμ΄λ : 골λ 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 |
'Algorithm λ¬Έμ > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[c++] BOJ 12888 :: μμ μ΄μ§ νΈλ¦¬ λλ‘ λ€νΈμν¬ (0) | 2021.07.20 |
---|---|
[c++] BOJ 18240 :: μ΄μ§ νμ νΈλ¦¬ 볡μνκΈ° (0) | 2021.07.11 |
[c++] BOJ 3584 :: κ°μ₯ κ°κΉμ΄ κ³΅ν΅ μ‘°μ (0) | 2021.07.03 |
[c++] BOJ 5052 :: μ νλ²νΈ λͺ©λ‘ (0) | 2021.07.03 |
[c++] BOJ 1600 :: λ§μ΄ λκ³ ν μμμ΄ (0) | 2021.06.25 |
Comment