[BOJ] 2912번: PATULICI

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


세그먼트 트리에서 구간을 나누는 것과 같이 구간을 나눕니다. 이제 각 구간에는 해당하는 구간에서 절반을 초과한 색깔을 저장합니다. 이는 맨 처음 색을 다 입력받은 후 재귀적으로 트리를 만드는 방법으로 저장할 수 있습니다. 주어진 쿼리에 해당하는 구간을 세그먼트 트리대로 쪼개고 나면, 반드시 어느 한 구간에서는 정답인 색깔이 가장 많이 등장해야 합니다. 그러므로 각 쿼리에 대해 최대 $lg N$개의 색에 대해 확인을 하면 됩니다.


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

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

[BOJ] 1941번: 소문난 칠공주  (0) 2018.11.19
[BOJ] 2553번: 마지막 팩토리얼 수  (2) 2018.11.18
[BOJ] 15329번: Secret of Chocolate Poles  (0) 2018.11.14
[BOJ] 2912번: PATULICI  (4) 2018.11.14
[BOJ] 1849번: 순열  (0) 2018.11.14
[BOJ] 2236번: Team Selection  (0) 2018.11.13
[BOJ] 1762번: 평면그래프와 삼각형  (0) 2018.11.12
  Comments
댓글 쓰기