[백준] 1949번 우수 마을 C++

1949번: 우수 마을 1949번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 검색 우수 마을 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 5523 2691 1901 51.686% 문제 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어... www.acmicpc.net 트리 dp를 활용하는 문제 dp[i][2]로 해서 0이면 우수 마을 1이면 안 우수 마을이다. dp[i][0]은 i가 우수마을 일 때의 최댓값이다. i가 우수 마을 일 때는 접해있는 마을이 안 우수 마을이어야 하기에 dp[i][1]을 더해준다. dp[i][1]은 i가 우수 마을이 아닐 때의 최댓값이...

원문링크 : [백준] 1949번 우수 마을 C++