7889번 - 힙 세기
문제에서는 자식이 항상 부모보다 작은 max-heap 구조라고 설명하고 있는데요. (아래 발췌 내용 참고)
> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙여있는 숫자는 부모의 정점에 붙어잇는 숫자보다 작다.
예시나 테스트 케이스를 살펴 보았을 때 min-heap 구조인 것 같습니다.
대표적인 예시로 테스트 케이스를 보면,
i+1번 정점의 부모의 번호가 주어진다고 하였으나, 문제에서 주어진 테스트 케이스를 보았을 때 2번과 3번 노드의 부모 번호가 1로 더 작은 것을 알 수 있습니다.
3 1000000 1 1
따라서 아래와 같이 수정되어야 합니다. (수정한 부분은 굵음 표시하였으며, 오타도 함께 수정하였습니다.)
> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙어있는 숫자는 부모의 정점에 붙어있는 숫자보다 크다.
댓글을 작성하려면 로그인해야 합니다.
hyojin_joo 1년 전 1
문제에서는 자식이 항상 부모보다 작은 max-heap 구조라고 설명하고 있는데요. (아래 발췌 내용 참고)
> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙여있는 숫자는 부모의 정점에 붙어잇는 숫자보다 작다.
예시나 테스트 케이스를 살펴 보았을 때 min-heap 구조인 것 같습니다.
대표적인 예시로 테스트 케이스를 보면,
i+1번 정점의 부모의 번호가 주어진다고 하였으나, 문제에서 주어진 테스트 케이스를 보았을 때 2번과 3번 노드의 부모 번호가 1로 더 작은 것을 알 수 있습니다.
따라서 아래와 같이 수정되어야 합니다. (수정한 부분은 굵음 표시하였으며, 오타도 함께 수정하였습니다.)
> 같은 번호를 가지는 정점은 없고, 힙을 형성하고 있다. 즉, 각 정점에 붙어있는 숫자는 부모의 정점에 붙어있는 숫자보다 크다.