합주단 곰곰
면접 대비시간 제한1초메모리 제한1024 MB
N명의 단원이 K개의 음 중 하나를 같은 확률로 고를 때, 같은 음을 연주하는 쌍의 기대값을 구합니다.
문제
곰곰은 실로폰을 아주 잘 친다.
곰곰이 실로폰 채로 건반을 치는 순간, 주변 사람들의 관심은 실로폰의 청아한 소리에 모인다.
곰곰은 이 재능으로 사람들을 행복하게 하려고 합주단을 만들었다. 합주단에는 곰곰이 많이 있고, 각 곰곰이 음 하나를 맡아 악보에 맞춰 연주한다.
곰곰의 실로폰은 같은 음을 여러 곰곰이 함께 연주할 때 더 청아한 소리가 난다. 그래서 같은 음을 내는 곰곰끼리 조를 만들기로 했다.
연주를 성공적으로 마친 합주단원들은, 각 조원이 자신을 제외한 다른 조원 한 명 한 명과 단둘이 밥을 먹으며 친해지는 시간을 가진다.
식사 비용은 합주단장 곰곰이 부담하므로, 공연 전에 필요한 금액을 미리 알아두어야 비용을 준비할 수 있다.
그런데 아직 연주할 악보가 정해지지 않아서, 한 조에 몇 명이 들어갈지 알 수 없고 정확한 비용도 계산할 수 없다.
그래서 곰곰 단장은 일어날 수 있는 식사 횟수의 기댓값을 구해, 그만큼의 비용을 준비하려고 한다.
각 곰곰이 연주할 음은 음의 개수 개 중에서 같은 확률로 정해진다고 가정한다.
단원들이 밥을 먹지 못하는 일이 없도록 곰곰 단장을 도와주자!
입력
합주단원의 수 (), 곰곰이 연주할 수 있는 음의 개수 ()가 차례로 주어진다.
출력
식사가 일어나는 횟수의 기댓값을 출력한다. 절대 오차 또는 상대 오차는 까지 허용한다.