구슬 분배 > 문제은행

본문 바로가기


실전대비 Level5

1446 : 구슬 분배

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 20 회    시도횟수: 48 회   



N 개의 모양이 서로 다른 구슬이 있다 편의상 이 구슬들에 1, 2, 3 , . . . N의 번호를 붙였다고 생각을 하자. 이제 구슬들을 M개의 그룹으로 분할하는 일을 해야 하는데, 그 전에 구슬들을 M개의 그룹으로 분할하는 경우의 수를 구하고 싶다. 단, 한 개의 그룹에는 적어도 한 개 이상의 구슬이 들어가야 한다.

 

예를 들어, N = 4, M = 2 일 때에는

 

{1, 2} {3, 4}   {1, 3} {2, 4}
{1, 4} {2, 3}   {1} {2, 3, 4}
{1, 3, 4} {2}   {1, 2, 4} {3}
{1, 2, 3} {4}

 

위와 같이 7가지 경우가 존재한다. 참고로, {A, B} {C, D} 로 나누는 것이나, {C, D} {B, A}로 나누는 것이나 같은 경우가 된다. 하지만, 이 구슬들 중 가장 아름다운(?) 구슬과, 가장 괴상한(?) 구슬이 같은 그룹에 속하게 되는 일은 그다지 바람직한 현상이 아니므로, 이 경우는 제외하고 경우의 수를 세어야 한다. 즉, 위의 예에서 가장 아름다운 구슬과 가장 괴상한 구슬이 각각 1과 4라면 위의 경우들 중 밑줄로 표시된 경우들만 가지 수를 세므로, 우리가 찾고자 하는 답은 4가지이다. (1과 4는 서로 다른 그룹에 들어간다)

 

N, M과 가장 아름다운 구슬, 가장 괴상한 구슬이 주어질 때 총 가지 수를 계산하는 프로그램을 작성하라.


첫 줄에 정수 N(3≤N≤1,000)와 정수 M(1≤M≤1,000) 주어지고, 둘째 줄에는 가장 아름다운 구슬의 번호 P와 가장 괴상한 구슬의 번호 Q가 한 칸의 공백을 두고 주어진다. P, Q는 모두 1 이상 N 이하의 정수이다.


출력 파일의 첫 줄에는 구하고자 하는 경우의 수를 반드시 한 개의 정수로 출력해야 하는데, 경우의 수가 너무 많을 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

[Copy]
4 2
1 4
[Copy]
4




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.