Leta Learns

문제 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 스터디 할 때 트리 DP 예제 코드를 받아놔서 그거 보고 좀 고치면서 풀었더니 골드1 치고는 엄청 빨리 풀었다. 사실 두 시간 만에 푼 거라 난이도 떠나서도 내 기준 엄청 빨리 푼 편에 속한다. 문제 이해부터 쉽지 않았는데, 문제에서 중요한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우..

골드1... 함부로 건드리면 안된다... 진짜... 문제부터 잘 이해가 안 돼서 계속 읽었다. 겨우겨우 이해한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우수 마을 일 수 없다. 루트 노드가 우수 마을이 아니면, 하위 노드는 우수 마을이거나 아니거나. (둘 중 최댓값....아마도) 이걸 dp에 저장하는 게 역시나 난관이었는데 dp[i][0] : 현재(i) 마을이 우수 마을이 아닌 경우 dp[i][1] : 현재(i) 마을이 우수 마을인 경우 로 저장했다. 제출했는데 recursion error 떠서 절망적이었다.. 근데 recursionlimit 풀어주니까 바로 됐다. 사실.. 어떻게 이렇게 빨리 풀 수 있었..

1. Tree DP Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나) => 그래프처럼 DP 기법 적용 가능 트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다. 트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적. => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함. 기본적으로 Top-down 방식으로 코드 작성. => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식. Tree DP 예제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 ..