공 칠하기
-
백준 1538 공 칠하기문제 2023. 7. 8. 20:59
https://www.acmicpc.net/problem/1538 1538번: 공 칠하기세준이는 가방을 하나 가지고 있다. 이 가방 속에는 N개의 공이 들어있다. N개의 공엔 색이 칠해져 있다. 세준이는 이 가방에서 서로 다른 두 개의 공을 하나씩 차례대로 고른다. 그 후에 두 번째www.acmicpc.net순서를 고려하지 않고 $N$을 자연수의 합으로 분할하는 방법 한 가지는 가방 속 공의 상태와 대응된다. 이 '상태'를 적절히 표현해보자. 예를 들어 $N=5$일 때, 아래와 같은 7가지 상태가 가능하다.$$(5), (3, 2), (4, 1), (2, 2, 1), (3, 1, 1), (2, 1, 1, 1), (1, 1, 1, 1, 1)$$어떤 상태 $\sigma$에서 시작했을 때의 기댓값을 $D_\si..