SY DevLog

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다. 중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다. 1 - 6 - 4 - 3 - 5 - 2 - 7 즉, 전체 트리에 루트 노드는 3번이다. 그 다음 3을 기준으로 왼쪽(1 - 6 - 4)는 왼쪽 자식 트리를 중위순회한 결과이며, 오른쪽(5 - 2 - 7)은 오른쪽 자식 트리를 중위순회한 결과이다. 각각의 자식 트리도 ..

1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 트리에서 다이나믹 프로그래밍을 이용하여 푸는 문제다. dfs방식으로 루트노드에서부터 리프노드까지 top - down 으로 내려간 후, 다시 리프노드에서부터 위로 올라가면서 dp배열을 업데이트한다. dp배열은 이차원 배열로 생성하여서 n번 마을이 우수 마을인 경우와 그렇지 않은 경우로 나누었다. dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합 dp[n][1] : n번 마을이 우수 ..