트리에서의 다이나믹 프로그래밍3 [백준] 14267: 회사 문화 1 - JAVA https://www.acmicpc.net/problem/14267 풀이상사가 직속 부하를 칭찬할 수 있는데 a가 b에게 10의 칭찬을 했다면 b의 직속 부하인 c도 10의 칭찬을 받는 것이 된다. 각 번호의 직원마다 직속 상사의 번호가 주어져 저장했다. 직속 상사로부터 칭찬을 받은 직원의 번호와 칭찬 수치가 주어지는데, int배열을 만들어 저장했다. 1번이 사장이므로 1번부터 시작하여 트리를 타고 내려가면서 int배열의 값을 부모 노드에서 자식 노드에 더해주는 식으로 구현했다. 메모리: 76068KB시간: 792ms언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> list; static i.. 2024. 5. 19. [백준] 13325: 이진 트리 - JAVA https://www.acmicpc.net/problem/13325 풀이포화이진트리의 에지들에 가중치가 있을 때, 에지들의 가중치를 증가하여 루트에서 리프까지의 거리가 같게 만들어야 한다. 트리의 높이 k 가 주어지는데 이때 트리의 사이즈는 Math.pow(2, k + 1) - 1 이다. 사이즈만큼 배열을 만들어 arr[2]부터 채운다. arr[1]은 루트노드로 값은 0이다. 문제에서는 에지에 가중치가 있다고 표현하고있지만 각 노드들에 가중치를 넣었다. 배열을 채운 후, 루트노드 1 부터 시작하여 dfs탐색을 통해 값을 더한다. 왼쪽 자식 노드와 오른쪽 자식 노드의 값 중 큰 값을 현재 노드의 값에 더해 부모 노드로 반환하고, 답을 저장하는 변수에 현재 노드의 값과 왼쪽 자식, 오른쪽 자식의 차를 더한다.. 2024. 5. 14. [백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다. 메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13. 이전 1 다음