zyechun   2년 전

안녕하세요

0을 루트노드로 가정하고

state가 0일 때 -> max(자식노드 선택하기, 자식노드 선택 안하기)

state가 1일 때 -> 자식노드 선택 안하기

parent면 넘어가기

이렇게 구현해서 9%까지 통과했는데 어디가 틀렸는지 모르겠어요

도와주세요..

ainch96   2년 전

res 벡터를 만드는 부분이 이상합니다. 현재 노드가 지역 최적해를 구성하는 노드일 경우 바로 push back을 하고 있는데 지역해가 더 크다고 해서 답의 일부분 이라는 것은 보장 되어 있지 않기 때문에 push_back을 하면 알될 것 같습니다. 



4 3 1

1 2 

2 3 

일 경우 dfs로 2,3 을 탐색하고 현재 정점이 2일 

2번 정점만 선택한 경우가 3번 정점만 선택한 경우보다 더 큰 가중치를 가지기 때문에 2를 push_back 합니다.

하지만 최적해는 1,3 노드로 구성되어있습니다. 이상한 점을 눈치채셨나요?

이 문제를 해결 하려면 각각의 dp가 어떤 dp값을 참조해서 생성된 것인지 확인한 다음 역추적을 해가야합니다. 

zyechun   2년 전

자세한 답변

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.