BaaaaaaaarkingDog
코딩, 해킹
[BOJ] 17513번: Hilbert's Hotel

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

 

대회중에는 풀어내지 못했던 문제입니다. group의 시작 위치를 $ax+b$꼴의 segment tree로 관리하면 1, 2번 쿼리의 처리가 가능하고, 또 group이 추가될 때 마다 유한한 그룹은 묶어서 관리하면 3번 쿼리에 대해 최대 30개의 그룹 묶음을 확인하면 됨을 알 수 있습니다. 그룹 묶음 내에서 정확한 그룹을 찾기 위해서는 binary search를 이용해야 합니다.

 

3번 쿼리의 구현이 개념이 엄청 어려운건 아닌데 이상하게 계속 틀려서 정말 까다로웠습니다.

 

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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 15293번: Knapsack Cryptosystem  (0) 2019.10.21
[BOJ] 15896번: &+ +&  (0) 2019.10.15
[BOJ] 17513번: Hilbert's Hotel  (0) 2019.10.15
[BOJ] 10464번: XOR  (0) 2019.09.12
[BOJ] 16685번: XOR 포커  (0) 2019.09.12
[BOJ] 11191번: XOR Maximization  (0) 2019.09.12
[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
  Comments
댓글 쓰기