[java] 백준 1949 (우수 마을) Gold 1

문제 원문 링크 : https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net Approach(Wrong: TLE) 트리에서의 DP문제로, 2213번 트리의 독립집합과 유사한 문제이다. DFS를 이용하여 트리 끝까지 내려가면 함수가 차례차례 종료되는 것을 이용하여 값을 갱신했지만 시간초과(TLE)가 떴다. 질문 글을 올려 답변을 받자면 내 잘못된 코드는 DP를 수행하지 않고 그냥 탐색만 하는 것이므로 각 호출에서 구한 답을 메모이제이션 해보라는 ..

→2020.12.13

Algorithm/Baekjoon Online Judge

[java] 백준 15681 (트리와 쿼리) Gold 5

문제 원문 링크 : https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net Approach 트리에서의 DP문제다. 트리를 만들 때는 루트를 지정하고 시작하는 것이 편하다. 이 문제의 경우에는, 트리를 만들면서 배열에 자신의 서브노드 개수를 기록하면 된다. 함수를 재귀적으로 호출하면 Terminal Node부터 함수가 종료되기 때문에 쉽게 구현할 수 있다. Code import java.io..

→2020.12.12

[java] 백준 1949 (우수 마을) Gold 1

[java] 백준 15681 (트리와 쿼리) Gold 5

티스토리툴바