skynet   8달 전

힌트로 dp가 나왔는데 어떤 방식으로 접근을 해야 할지 모르겠습니다. ㅠ.ㅠ

어떤 정보를 저장해야 할지 모르겠어요 ㅠㅠ

다음 소스에 대한 예외 테스트 케이스 생성도 부탁드립니다. ㅠㅠ

zlzmsrhak   8달 전

트리의 루트를 임의로 정하고, dp 테이블의 정의를

A[i]: i번째 노드를 루트로 하는 부트리에서 i를 선택했을 때의 최댓값

B[i]: i번째 노드를 루트로 하는 부트리에서 i를 선택하지 않을 때의 최댓값

으로 접근해보세요.

--

반례 데이터

4

18 17 15 4 

2 1

3 1

4 2

답: 32

skynet   8달 전

감사합니다.

yhms4432   2달 전

트리를 따로 정의안하고 dp테이블만 가지고 풀수 있나요??

skynet   2달 전

트리는 그냥

그래프 형식(간단한 array 또는 vector) 구성하고


선택 했을때 최대값, 선택 안했을때 최대값

dpTable 을 2개 만들어서 접근하면 될거 같습니다.


지금도 못하지만 6개월전에는 더못해서 struct를 만들어서 했네요 ㅋㅋz


yhms4432   2달 전

감사합니다!!!^^

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