filot   1년 전

최소로 수로 지붕을 채울 수 있는 경우의 수를 구해서

당시에 선택된 color에 해당하는 페인트의 비용을 더해 주었는데

(페인트는 비용이 적게 드는 것부터 선택하는게 좋으니 정렬을 해버렸습니다.)

틀리다고 하네요.. ㅠㅠ

zlzmsrhak   1년 전

일단 반례입니다. 알고리즘만 봤을 때는 제가 예상한 출력은 303이고, 답은 204입니다.

트리는 항상 2개의 색으로 칠하는 것이 가능합니다.

filot   1년 전

감사합니다.

제가 정답이 경우에 해당하는 경우를 저장하지 않았네요.

그런데도 제출한 하면 틀리네요.

뭔가 예외 케이스가 있을 듯 한데.. 찾기가 쉽지 않네요.

zlzmsrhak   1년 전

제가 올린 예제의 답은 204인 것 같습니다. 

 2,3번을 각각 2, 3번 색으로 칠하고, 나머지를 1번색으로 칠하면 204가 나옵니다

filot   1년 전

에휴잘안되네요.. 푸신분 힌트라도 좀 얻을 수 없을까요?

zlzmsrhak   1년 전

트리DP를 사용하고, 테이블로는 D[v][c] : v번째 정점을 c로 칠했을 때, v의 부트리를 칠하는 최소 비용

으로 점화식을 세워보세요

filot   1년 전

DP군요.. 넵 감사합니다.

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