19, Max-plus tree(14점)
작성자
kangcoding
작성일
2024-05-05 23:54
조회
487
아래와 같이 루트가 있는 트리가 하나 주어진다. 아래 그림에서 가장 위에 있는 정점이 루트 정점, 아래에있는 16개의 팔각형 형태 정점이 리프 정점이다.
리프 정점이 아닌 정점, 즉 14개의 내부 정점은 각각 max 정점 또는 plus 정점 중 하나로 지정되어 있다. max 정점은 원, plus 정점은 사각형, 리프 정점은 팔각형으로 표시한다.
각 정점의 값은 리프 정점에 배정된 값에 따라 결정된다. 리프 정점의 값은 리프 정점에 배정된 수이고, max 정점의 값은 자식 정점들의 값의 최댓값이며, plus 정점의 값은 자식 정점들의 값의 합이다.
당신은 16개의 수를 리프 정점에 배치해서 루트 정점의 값을 최대화해야 한다.
아래에서 직접 리프 정점에 수를 배치할 수 있다. 하단에 있는 수를 마우스로 드래그해서 리프 정점에 배치할 수 있다. 각 수는 최대 한 번씩 사용할 수 있다. 수를 리프 정점 바깥으로 이동시키면 수를 제거할 수 있다.
각 정점의 값은 정점 도형 안에 표시된다. 만약 리프 정점에 수가 배치되지 않았다면 그 정점의 값은 0으로 취급한다.
모든 리프 정점에 수가 배치되지 않은 경우 점수를 받지 못함에 주의해야 한다.
채점 방식
모든 리프 정점에 수가 배치되었고 루트 정점의 값이 최대이면 전체 점수의 100%를 받는다.
========== 풀이 ==========
1번의 최대 값이 되기 위해서는 2번과 3번이 최대값이 되어야 한다.
2번은 4번과 5번중 최대값이 올 수 있는데 5번은 4번에서가 최대값을 한번 더 더할 수 있으므로 4번을 최대값을 만드는게 좋다.
숫자를 다음과 같이 배치하면 최대값 81을 만들 수 있다.
리프 정점이 아닌 정점, 즉 14개의 내부 정점은 각각 max 정점 또는 plus 정점 중 하나로 지정되어 있다. max 정점은 원, plus 정점은 사각형, 리프 정점은 팔각형으로 표시한다.
각 정점의 값은 리프 정점에 배정된 값에 따라 결정된다. 리프 정점의 값은 리프 정점에 배정된 수이고, max 정점의 값은 자식 정점들의 값의 최댓값이며, plus 정점의 값은 자식 정점들의 값의 합이다.
당신은 16개의 수를 리프 정점에 배치해서 루트 정점의 값을 최대화해야 한다.
아래에서 직접 리프 정점에 수를 배치할 수 있다. 하단에 있는 수를 마우스로 드래그해서 리프 정점에 배치할 수 있다. 각 수는 최대 한 번씩 사용할 수 있다. 수를 리프 정점 바깥으로 이동시키면 수를 제거할 수 있다.
각 정점의 값은 정점 도형 안에 표시된다. 만약 리프 정점에 수가 배치되지 않았다면 그 정점의 값은 0으로 취급한다.
모든 리프 정점에 수가 배치되지 않은 경우 점수를 받지 못함에 주의해야 한다.
채점 방식
모든 리프 정점에 수가 배치되었고 루트 정점의 값이 최대이면 전체 점수의 100%를 받는다.
========== 풀이 ==========
1번의 최대 값이 되기 위해서는 2번과 3번이 최대값이 되어야 한다.
2번은 4번과 5번중 최대값이 올 수 있는데 5번은 4번에서가 최대값을 한번 더 더할 수 있으므로 4번을 최대값을 만드는게 좋다.
숫자를 다음과 같이 배치하면 최대값 81을 만들 수 있다.
전체 0