Joonas' Note

Joonas' Note

BOJ 1539 - 이진 검색 트리 본문

알고리즘/문제 풀이

BOJ 1539 - 이진 검색 트리

2020. 4. 17. 19:15 joonas

    링크: 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