“나가리” 회사의 조직도는 tree 구조를 갖고 있습니다. 즉, 사장을 root로 하고 직원들은 직속상관 바로 밑에 매달립니다. 이 회사에서 파티를 열려고 하는데 파티의 분위기를 위해 부하직원과 그 직속상관은 같이 파티에 초대될 수 없도록 하려고 합니다. 각 직원들의 “날라리 기질”은 평소 관찰을 통해 회사의 데이터베이스에 기록이 되어 있습니다. 위의 제한을 만족시키면서 파티의 날라리 분위기(참가자들의 날라리 기질의 합)가 최대가 되도록 참가자 목록을 결정하는 선형시간(linear-time, O(n) time) dynamic programming 알고리즘을 고안하세요.
형들아 나이거땜에 며칠째 죽을것 같아 나좀 도와조ㅠㅠ
정말 포기하고 싶다......12시까지 해야되는데 멋진 형들아 좀 도와주셈
고냥 알고리즘책에 나오는그림을 말로 바꿧을뿐이야;
postorder walk 하면서 해당 노드가 참가했을때/참가하지 않았을때 날라리 최대치 구하면 되겠네. 루트까지 올라가면 사장이 참석/불참했을때 값 나오니까 둘 중 큰거 출력하면 되고. postorder walk 하고 각 노드에서 상수 시간밖에 안 잡아먹으니 O(n).
N:직원, V(N):N의 날라리값, X(N):N이 참석했을때 날라리값, Y(N):N이 불참했을때 날라리값, C[i](N):N의 i번째 부하직원
X(N):=sum{i}(Y(C[i](N))+V(N), Y(N):=sum{i}(X(C[i](N)) 답은 max{X(root),Y(root)}
이해는 안가지만 너무 고마워 횽 나두 횽처럼 잘하고 싶다.....
헉... Y(N):=sum{i}(max{X(C[i](N)),Y(C[i])(N))})이다... 실슈
상사가 참석 안한다고 부하직원이 무조건 참석할 필요는 없지.
ㅆㅂ.. 다시 정리.. X(N):=sum{i}(Y(C[i](N)))+V(N), Y(N):=sum{i}(max{X(C[i](N)),Y(C[i](N))}) 답은 max{X(root),Y(root)}