문제
3272 문제에서 N을 10까지 확장하고 사용가능한 메모리를 줄여서 도전해보자.
1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다.
3. 3번 기둥에 모든 원판이 모이면 더 이상 원판을 이동시킬 수 없다.
모든 원판이 1번 기둥에 순서대로 쌓여 있을 때,
M번 이하의 이동횟수로 3번 기둥으로 모두 이동하는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫 행에 원판의 수 N과 이동횟수 M이 공백을 구분하여 주어진다.
(1 <= N <=10, 1 <= M <= 1,500)
출력
M번 이하의 이동횟수로 3번 기둥으로 모두 이동하는 경우의 수를 10억 7로 나눈 나머지를 출력한다.
예제 #1
10 1024
513
예제 #2
10 1200
362869054
출처
JKJeong
로그인해야 코드를 작성할 수 있어요.