BOJ 1539 - 이진 검색 트리

Joonas' Note

BOJ 1539 - 이진 검색 트리 본문

알고리즘/문제 풀이

BOJ 1539 - 이진 검색 트리

2020. 4. 17. 19:15 joonas 읽는데 1분
  • 문제
  • 코드

링크: https://www.acmicpc.net/problem/1539

문제

주어진 순서대로 이진 검색 트리를 구축하였을 때, 모든 노드들의 높이 합을 출력하는 문제이다.


9 다음에 1이 주어지면, 위와 같은 그림일 것이다.

다음으로 4가 들어오면 x 위치로 갈 텐데, 이전에 등장한 수 중에서, 자신보다 바로 작거나 바로 큰 수의 높이 중 더 큰쪽 + 1이 자신의 높이이다.

만약 y 자리에 무엇이 있다고 해도, x<9<y 임은 항상 보장되므로, 자신보다 바로 작거나 큰 수만 비교하면 된다.

코드


'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 15480 - LCA와 쿼리  (0) 2020.05.15
BOJ 9034 - 순위  (0) 2020.05.01
BOJ 18109 - 도깨비불  (0) 2020.04.02
SWEA 2112 - [모의 SW 역량테스트] 보호 필름  (0) 2020.02.26
SWEA 4254 - 가장 큰 수 만들기  (2) 2020.02.25
Comments