2225번 - 합분해
0~N까지의 정수를 k개를 써서 N을 만들 수 있는 경우를 구하는 문제인데,
N+1개 (0~N)인 이유는 알겠고, 왜 H(중복조합)을 쓰는지 알겠는데, n+1HK-1 , 왜 K-1개를 뽑는 경우인가요 ?
K개를 사용해서 N을 구성해야하니까, n+1Hk 일거라고 전 생각합니다. 히지만, 답은 k-1이죠!
k-1 개의 공간이 생기는 경우라고 하는데, k-1개의 공간이 생기는 경우가 어떤 말을 하는지 잘 모르겠습니다..ㅠㅠ
제가 이해할 수 있도록 도와주실 분 있을까요?
감사합니다 .
일자 책상에 의자가 n개 놓여 있는데, 이걸 0칸 이상의 k개 그룹으로 나누는 상황입니다. 칸막이는 k-1개만 있으면 됩니다. 배치할 수 있는 위치는 가장 왼쪽 의자의 왼쪽부터, 가장 오른쪽 의자의 오른쪽, 총합 n+1개입니다.
감사합니다! 추가질문 드릴 수 있을까요!
일자 책상에 의자 n개 놓여있고, 0칸 이상의 k개 그룹으로 나누는 상황이라고 한다는 중복순열로 접근을 한다는 말이라고 이해했습니다.
말씀주신대로, "k-1" 개의 칸막이 + "n+1"개의 자리이기 때문에, 경우의 수를 계산해주면,(n+k)!/(k-1)!*(n+1)! 입니다.
정답인 (n+k-1)!/(k-1)!*n!과 다른 값이 나오게 됩니다.
제가 어느 부분에서 잘못 생각하는 걸까요 ? 생각을 고쳐야하는 부분을 알려주실 수 있을까요?
아래 것이 답이 맞습니다. 중복조합 공식을 다시 찾아보시면 될 것 같습니다.
감사합니다. 이해했습니다.
댓글을 작성하려면 로그인해야 합니다.
wnsrl4067 2년 전
0~N까지의 정수를 k개를 써서 N을 만들 수 있는 경우를 구하는 문제인데,
N+1개 (0~N)인 이유는 알겠고, 왜 H(중복조합)을 쓰는지 알겠는데, n+1HK-1 , 왜 K-1개를 뽑는 경우인가요 ?
K개를 사용해서 N을 구성해야하니까, n+1Hk 일거라고 전 생각합니다. 히지만, 답은 k-1이죠!
k-1 개의 공간이 생기는 경우라고 하는데, k-1개의 공간이 생기는 경우가 어떤 말을 하는지 잘 모르겠습니다..ㅠㅠ
제가 이해할 수 있도록 도와주실 분 있을까요?
감사합니다 .