[BOJ] 14794번: Bathroom Stalls

https://www.acmicpc.net/problem/14794

맨 처음에 다른 문제(https://www.acmicpc.net/problem/10755) 와 착각해서 굉장히 어려운 문제라고 착각을 했는데 다행히 Binary Search Tree로 그럭저럭 쉽게 풀이가 가능한 문제였습니다.

핵심 아이디어는 연속된 구간의 길이를 key로 하고, 구간의 갯수를 value로 하는 Map을 만들어, 가장 긴 구간을 뽑아서 쪼개는 것을 반복하는 것입니다.

예를 들어 1024 100이라고 한다면 map은

i) (1024, 1) (처리한 사람 = 0명)

ii) (512, 1), (511,1) (처리한 사람 = 1명)

iii) (511,1) (256,1), (255,1) (처리한 사람 = 2명)

iv) (256,1), (255,3) (처리한 사람 = 3명)

.

.

.

이런식으로 진행해서 처리한 사람이 100명이 됐을 당시에 쪼개는 구간이 어디인지 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/14794.cpp