프로그래밍

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

[난이도] Gold3
[유형] 트리

[풀이]
각 노드가 몇개의 인접한 노드를 가지고 있는지와 N-1개의 간선 (u,v) 만
저장해주면 문제를 풀 수 있습니다.
acnt[300001] 배열을 선언하여 acnt[i] : i번 노드와 연결된 노드 개수로 정의한 뒤 값을 저장해주었습니다.

D-트리의 개수 : 모든 간선 N-1개의 (u,v) 에 대해 (acnt[u]-1) * (acnt[v]-1) 의 값을 더해주면 됩니다.
                u와 연결된 u`, v와 연결된 v`을 이용해 [u` - u - v - v`] 형태의 D 트리를 만들 수 있습니다.
                1을 빼주는 이유는 [u-v] 간선을 빼주는 것입니다.

G-트리의 개수 : 1~N번 노드 i에 대해 조합 acnt[i]C3 을 구해주면 됩니다.
                acnt[i] 중 3개를 뽑으면 i 중심으로 3개의 간선이 연결된 트리가 되기 때문입니다.

#include <cstdio>
#include <vector>
using namespace std;
int N;
int acnt[300001];
vector<pair<int,int>> p;
int main(){
    scanf("%d",&N);
    for(int i=1;i<N;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        acnt[u]++, acnt[v]++;
        p.push_back({u,v});
    }
    long long a=0,b=0;
    for(auto [u,v] : p) a+=(acnt[u]-1)*(acnt[v]-1);
    for(int i=1;i<=N;i++) if(acnt[i]>=3) b+=(acnt[i]*(acnt[i]-1)*(acnt[i]-2))/6;
    b*=3;
    if(a>b) puts("D");
    else if(a<b) puts("G");
    else puts("DUDUDUNGA");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/19535.cpp

https://programmers.co.kr/learn/courses/30/lessons/68937

[난이도] level4
[유형] 트리

[풀이]
트리의 지름을 이용하여 해결하는 문제입니다.
트리의 지름이란 트리에서 가장 먼 두 점 a,b의 경로를 의미합니다.
임의의 점 x에서 가장 먼 점 y를 구하고 y에서 가장 먼 점 z를 구하면 y-z의 경로가 트리의 지름이 됩니다.
( https://blog.myungwoo.kr/112 블로그를 참고하시면 자세한 설명이 있습니다.)

문제의 주어진 트리에서 지름이 y-z1, y-z2 이렇게 두가지가 있다면
정답은 트리의 지름의 길이가 됩니다. 왜냐하면 세 점을 y , z1, z2 이렇게 정하면
z1-z2의 거리는 트리의 지름인 y-z1,y-z2보다 길어질 수 없기 때문에 y-z1의 길이가 무조건 중간값이 됩니다.

만약 트리의 지름이 y-z 한개밖에 나오지 않는다면 z에서 다시한번 트리의 지름을 구해봅니다.
만약 이때 위의 경우처럼 두가지가 나온다면 마찬가지로 트리의 지름의 길이가 중간값이 되고,

만약 이때도 한가지만 나온다면 (트리의 지름의 길이 -1)이 정답이 됩니다.
왜냐하면 트리의 지름이 단 한가지 경로만 존재하는 경우이며 이것보다 같거나 긴 경로는 없습니다.
그러므로 트리의 지름 y-z 에서 z와 인접한 점 w를 정해야 하는 나머지 한 점으로 설정하면
y-w-z 형태의 경로가 나오게 되고, y-z,y-w,w-z 중에 y-w가 (y-z의 길이 -1)로, 구해야 하는 중간값이 됩니다.

#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[250001];
priority_queue<int> pq;
int mxD,from;
void dfs(int p,int m,int cnt,bool f){
    if(mxD < cnt){
        mxD=cnt;
        from=m;
    }
    if(f && adj[m].size()==1) pq.push(cnt);
    for(auto nxt : adj[m])
        if(nxt!=p) dfs(m,nxt,cnt+1,f);
}
int solution(int n, vector<vector<int>> edges) {
    for(auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    dfs(0,1,0,0);

    int a = from; mxD=0;
    dfs(0,a,0,1);
    int t=pq.top(); pq.pop();
    if(t==pq.top()) return t;
    while(!pq.empty()) pq.pop();

    a=from; mxD=0;
    dfs(0,a,0,1);
    t=pq.top(); pq.pop();
    return t==pq.top() ? t : t-1;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/트리_트리오_중간값.cpp

https://programmers.co.kr/learn/courses/30/lessons/77486

[난이도] level3
[유형] 트리

[풀이]
칫솔 판매원(Leaf)부터 추천인을 거슬러 올라가면서 본인은 10%만큼, 추천인에게는 90%만큼 이익을 분배하면 됩니다.
전체 사람의 이름을 index로 매핑 시키면 쉽게 추천인을 찾을 수 있으므로 <String,Int> 타입의 맵을 선언하여
이름과 index를 매핑 하였습니다.

lateinit var answer:IntArray
lateinit var referral:Array<String>
var table = hashMapOf<String,Int>()
fun sol(name:String,v:Int){
    if(name=="-" || v==0) return
    var a = 0
    if(v%10!=0) a=1
    answer[table[name]!!]+=(0.9*v).toInt()+a
    sol(referral[table[name]!!],(0.1*v).toInt())
}
class Solution {
    fun solution(enroll: Array<String>, _referral: Array<String>, seller: Array<String>, amount: IntArray): IntArray {
        referral = _referral
        answer = IntArray(enroll.size)
        for(i in enroll.indices) table[enroll[i]]=i
        for(i in seller.indices) sol(seller[i],amount[i]*100)
        return answer
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/다단계_칫솔_판매.cpp

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

[난이도] Silver1
[유형] 트리

[풀이]
Preorder, Inorder, Postorder 순회를 구현할 수 있는지를 묻는 문제입니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N = 0
var a = Array<Pair<Int,Int>>(26){Pair(0,0)}
fun preorder(n:Int){
    if(n==-1) return
    print('A'+n)
    preorder(a[n].first)
    preorder(a[n].second)
}

fun inorder(n:Int){
    if(n==-1) return
    inorder(a[n].first)
    print('A'+n)
    inorder(a[n].second)
}

fun postorder(n:Int){
    if(n==-1) return
    postorder(a[n].first)
    postorder(a[n].second)
    print('A'+n)
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    N = readLine().toInt()
    repeat(N){
        val carr = readLine().split(' ').map{it[0]}
        var left = if(carr[1]=='.') -1 else carr[1]-'A'
        var right = if(carr[2]=='.') -1 else carr[2]-'A'
        a[carr[0]-'A'] = Pair(left,right)
    }
    preorder(0)
    println()
    inorder(0)
    println()
    postorder(0)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1991.cpp