멜론은 국내 최다 고객과 음원을 보유한 디지털 뮤직 플랫폼이다.

멜론의 특징 중 하나는 사용자 개인별 맞춤 큐레이션 서비스로,

사용자의 취향 및 콘텐츠의 특성을 분석하여 좋아할 만한 음악을 추천함으로써 사용자가 계속해서 쓸 수 있는 서비스를 만드는 것이다.

사용자가 만족할 만한 서비스를 제공하기 위해서는 추천 알고리즘의 성능을 우수하게 유지하는 것이 중요하기 때문에,

사용자의 피드백에 따라 추천 알고리즘을 개선하거나, 좋은 성능을 보일 수 있는 새로운 추천 알고리즘을 고안하는 과정이 필요하다.

프로도는 사용자가 좋아할 만한 음악을 추천하기 위한 새로운 추천 알고리즘을 고안했다.

이 알고리즘은 음악 간 유사도를 트리의 형태로 만든 뒤 사용자의 입력에 따라 추천할 음악을 결정하는 방식이다.

예를 들어, 음악 간 유사도를 표현한 다음 트리를 살펴보자. 여기에서 각각의 노드가 곡을 나타내며, 노드의 색깔은 가수를 의미한다.

사용 패턴 분석을 통해 트리에 있는 노드 중 하나와 가중치가 결정되는데,

선택된 노드가 루트가 되는 서브트리의 모든 노드가 추천 대상이 된다.

이 서브트리에 속한 노드에 가중치에 따른 점수가 고르게 부여된다.

가중치가 노드의 수로 나누어떨어지지 않는 경우 몫만이 분배된다.

예를 들어, 아래 그림에서처럼 노드가 하나 선택되고 여기에 가중치 23을 부여한다고 가정해보자.

이 서브트리에 속한 노드는 총 다섯 개이고, 23을 5로 나누면 몫이 4가 되고 나머지가 3이 되기 때문에 각각의 노드에 점수 4가 부여된다.

이 점수가 높을수록 추천에서 선택될 확률이 높아진다.

이때, 특정한 가수의 곡만 추천되는 상황을 방지하기 위해 가수 별로 평균 점수를 관리하려고 한다.

위 트리에서 빨간색 벽돌 무늬로 표시된 노드가 아이유의 곡이라고 가정하자.

위의 그림과 같이 서브트리가 선택된 상황의 경우,

빨간색 노드가 총 두 개이므로 노드 하나당 4점씩 부여되어 아이유의 곡의 점수의 합은 8이 된다.

트리에서 빨간색으로 표시된 노드가 총 세 개이므로, 아이유의 곡은 평균 8/3점이 된다.

위와 같이 트리의 노드와 가중치가 선택되는 과정이 반복된다고 할 때,

가수 별 평균 점수가 주어진 목표 점수를 언제 초과하게 되는지 계산하려고 한다.

트리의 형태와 추천 알고리즘의 결과 데이터가 입력으로 주어질 때,

노드 별로 가수의 평균 점수가 목표 점수를 초과하는 시점을 계산하는 프로그램을 작성하시오.

음악 추천 timer 2s memory 1024MB

음악 추천 2s 1024MB