hyojin_joo   1년 전


문제에서는 자식이 항상 부모보다 작은 max-heap 구조라고 설명하고 있는데요. (아래 발췌 내용 참고)

> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙여있는 숫자는 부모의 정점에 붙어잇는 숫자보다 작다.


예시나 테스트 케이스를 살펴 보았을 때 min-heap 구조인 것 같습니다.

대표적인 예시로 테스트 케이스를 보면,

i+1번 정점의 부모의 번호가 주어진다고 하였으나, 문제에서 주어진 테스트 케이스를 보았을 때 2번과 3번 노드의 부모 번호가 1로 더 작은 것을 알 수 있습니다.

3 1000000
1
1

따라서 아래와 같이 수정되어야 합니다. (수정한 부분은 굵음 표시하였으며, 오타도 함께 수정하였습니다.)

> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙어있는 숫자는 부모의 정점에 붙어있는 숫자보다 크다.

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