취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25197번 문제인 합주단 곰곰이다.
문제는 아래 링크를 확인하자.

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

먼저, N마리의 곰곰이 각자 K개의 음중 하나를 선택하는 경우의 수는 K^N과 같다.

이중, 곰곰이 A와 곰곰이 B가 같은 음을 선택하는 경우의 수는 (K^(N-1))가지 있다.

따라서 곰곰이 A와 곰곰이 B의 쌍에 의해 추가될 식사횟수의 기댓값은 1/K와 같다.

기댓값의 선형성을 이용하면, 곰곰이 A와 곰곰이 B의 쌍은 N*(N-1)/2가지 있으므로 전체 식사횟수의 기댓값은 (N*(N-1)/2) / K와 같이 계산할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << fixed;
	cout.precision(10);

	int N, K; cin >> N >> K;
	cout << ((double)(N * (N - 1) / 2)) / K;
}