백준 15957번 - 음악 추천
https://www.acmicpc.net/problem/15957 15957번: 음악 추천 입력의 첫째 줄에는 세 정수로, 곡의 수 N(2 ≤ N ≤ 100,000), 추천 알고리즘의 결과 데이터의 수 K(1 ≤ K ≤ 100,000), 목표 점수 J(10 ≤ J ≤ 108)가 주어진다. 각각의 곡은 1번부터 N번까지 번호가 붙어 www.acmicpc.net 필요한 배경지식 병렬 이분 탐색(PBS), 펜윅 트리, 오일러 경로 테크닉 문제 해결 방법 [1,N] 번 노래를 부른 가수의 평균 점수가 J를 넘게 되는 시간을 각각 구하기 위해, 주워지는 쿼리를 이용하여 병렬 이분 탐색을 할 수 있습니다. 특정 노래를 부른 가수의 평균점수가 J점수를 언제 초과하는지 확인하기 위해 쿼리를 매개변수로 이분탐색을 하는..
알고리즘 공부/문제풀이
2021. 5. 29. 14:32
반응형