10722번 Binary Mobile Tree
문제
10722번 Binary Mobile Tree - 백준
설계
모빌의 크기를 구하는 문제인데 눈여겨볼 조건은 아래인 것 같다.
- 양수는 구슬 음수는 막대
- 1번 막대가 루트 노드 (-1)
- 구슬은 질량만 있고 부피는 없음
DFS를 사용해서 탐색하며 질량과 막대너비를 전달하면 되겠지 아마
구현
재귀호출하며 길이와 질량 정보를 받아 합친다.
왼쪽 질량 * 왼쪽 거리 == 오른쪽 질량 * 오른쪽 거리 공식에 따라 양쪽 거리를 구하고
서브트리가 반대로 퍼지는 걸 고려해서 좌우 폭을 구해 더해서 출력한다.
// DFS
tuple<double, double, double> DFS(int node, const vector<tuple<int, int, int>> &bar) {
// 양수면 구슬, 질량만 있음
if (node > 0) {
return {static_cast<double>(node), 0.0, 0.0};
}
// 음수면 막대
auto [len, l, r] = bar[-node];
auto [lm, ll, lr] = DFS(l, bar);
auto [rm, rl, rr] = DFS(r, bar);
double tm = lm + rm;
// 왼쪽 질량 * 왼쪽 거리 == 오른쪽 질량 * 오른쪽 거리
double ldist = len * (rm / tm);
double rdist = len - ldist;
// 서브트리가 반대로 퍼지는 경우를 고려해야함
double lw = min(-ldist - ll, rdist - rl);
double rw = max(-ldist + lr, rdist + rr);
return {tm, -lw, rw};
}
// ... 중략 ...
// 루트 노드는 -1
auto [mass, left, right] = DFS(-1, bar);
printf("%.6f\n", left + right);
채점
반성
auto 사용에 더 익숙해져야겠다.
좋은 건 잘 써먹어야지
엄청 깨끗하고 짧고 좋지 않은가?
코드 확인