Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
[LeetCode] 2872. Maximum Number of K-Divisible Components (C++)
EVEerNew 2023. 10. 12. 15:40문제
https://leetcode.com/problems/maximum-number-of-k-divisible-components/description/
Maximum Number of K-Divisible Components - LeetCode
Can you solve this real interview question? Maximum Number of K-Divisible Components - There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] ind
leetcode.com
풀이
난이도: HARD
DFS 문제.
subTree 노드들의 합이 k로 나눠지는 subTree의 최대 개수를 구하도록 edge를 끊어야 한다.
여기서는 수학적으로는 안되더라도 0은 k로 나눠지는 것으로 설정한다.
다음과 같은 트리에서는 1과 6의 edge를 끊어야, 모든 subTree가 4로 나눠질 수 있다.
특정 노드(여기선 0)를 root로 설정하고, DFS로 탐색을 시작한다.
일단 leaf node에 도달한 후,
자신으로부터 k로 나눌 수 있는 subTree를 만들 수 있다면 카운트를 증가시키고 부모에게 0을 반환하고
만들 수 없다면, 자신의 value까지 포함된 합을 부모에게 반환한다.
이때 자신으로부터 subTree를 만들 수 있더라도, 부모와 연결되어야 생성가능한 subTree 있지 않을까? 라는 생각이 들 수 있다.
부모와 연결해 주더라도 부모까지 합친 subTree의 합이 k로 나눠져야 하기 때문에, 결국 다시 k의 배수가 만들어져야 한다.
정답은 subTree를 최대 개수이므로 자신으로부터 subTree를 만들 수 있다면, 부모와 edge를 끊어주는 것이 항상 이득이다.
추가적으로 subTree sum이 int범위를 넘을 수 있으므로 변수는 long long으로 선언해주자.
솔직히 릿코드가 틀린 테스트 케이스를 보여주지 않았다면, 못 풀었을 것 같다.
코드