스파이 보내기 > 문제은행



실전대비 Level11

2072 : 스파이 보내기

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



강을 경계로 비토와 스턴 마을이 있었다. 

두 마을 사이에는 아무런 접촉도 없이 서로 고립되어 생활을 하고 있었다. 

그러던 중 스턴 마을에서는 스파이를 비토 마을에 보내기로 결정하였다. 

그러나 강을 건너 비토 마을로 들어갈 수 있는 배가 한척 밖에 없다. 

또한 이 배는 특이한 점을 가지고 있었다. 배는 항상 S명이 탑승해야 하며 비토 마을에 도착하면 

반드시 한 명만이 비토 마을에 남고 나머지는 다시 스턴 마을로 돌아와 S명을 태우고 다시 비토 마을로 갈 수 있다. 

다시 말하면 이 배는 다음과 같은 방법으로 운행된다.

· 처음 스턴 마을을 떠날 때 스파이 1, 2, ... , S명을 싣고 간다. 

그 중 한명이 비토 마을에 내리고 나머지 S-1명이 스턴 마을로 되돌아온다.
· 두 번째 스턴 마을을 떠날 때 스파이 S+1, S+2, ... , 2S와 되돌아 온 S-1명의 스파이를 싣고 비토 마을로 향한다. 

그들 중 한 명이 비토 마을에 내리고 나머지 2S-2명의 스파이 턴 마을로 되돌아온다.
· 세 번째는 스파이 2S+1, 2S+2, ... , 3S와 되돌아온 2S-2명의 스파이가 비토 마을로 향한다. 

그들 중 한 명이 비토 마을에 내린다.

이와 같이 계속한다. N번 비토 마을에 다녀온 후, 

파견된 스파이 N명을 구성하는 방법의 수를 모두 구하는 프로그램을 작성하시오.

 




한 줄에 한 번에 배에 탈 수 있는 사람의 수 S(1<=S<=10)와 배가 이동하는 횟수 N(1<=N<=40)이 주어진다.




한 줄에 스파이 구성원을 구성하는 방법의 수를 출력한다.

배에 탑승할 수 있는 사람의 수는 무한하다.
비토 마을에 도착하는 스파이들의 구성원 순서는 무관하다.



2 3
14


5 20
75134301594081389660






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.