스파이 보내기 > 문제은행



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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP