문제 링크입니다: https://www.acmicpc.net/problem/5817
5817번: 고통받는 난쟁이들
문제 옛날 옛적, 일곱 언덕과 일곱 바다를 건너 작은 마을이 있었어요. 백설공주는 놀고 먹고 자다가 일어나서 문명 5, 리그 오브 레전드, 풋볼 매니저를 하다가 다시 자는 난쟁이들 N명과 살고 있었어요. 계속되는 이런 생활에 진저리가 난 백설공주는 난쟁이들에게 고통을 주기로 결심했고, 체육 수업을 빙자한 얼차려를 주기로 했답니다! 수업이 시작할 때, 난쟁이들은 키가 큰 순서로 한 줄로 서 있어야 돼요. 신기하게도 난쟁이들 중 키가 같은 사람은 한 명도 없
www.acmicpc.net
최소, 최대 세그먼트 트리를 이용하여 푸는 문제였습니다.
1번 연산에 대해서는 기존에 알고 있던 최소, 최대 세그먼트 트리의 update를 적용하면 되고,
2번 연산에서는 굳이 합을 구하지 않아도 된다는 것이 핵심이였습니다.
합을 구하는 대신 최대 세그먼트 트리와 최소 세그먼트 트리를 이용하여 범위 내에 a ~ b가 다 있는지 확인만 하면 되는 문제였습니다.
*주의할 점은 최대, 최소 세그먼트 트리를 update할 때, 난쟁이들의 키가 인덱스고 난쟁이들의 위치가 배열의 값으로 두어야 한다는 점입니다!
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 10219번 Meats On The Grill (0) | 2019.05.28 |
|---|---|
| 백준 17176번 암호해독기 (2) | 2019.05.23 |
| 백준 4485번 녹색 옷 입은 애가 젤다지? (0) | 2019.05.22 |
| 백준 1238번 파티 (0) | 2019.05.22 |
| 백준 12116번 Uzastopni (0) | 2019.05.15 |