2516 : 컵 쌓기(Stacking Cup)
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 19 회
- 시도횟수
- 88 회
문제
다양한 크기의 컵 n개와 A, B, C 3개의 쟁반이 있다.
처음에 컵들이 쟁반에 거꾸로 쌓여있는데,
각 쟁반에 있는 컵은 가장 작은 컵이 아래에 있고,
그다음 두 번째로 작은 것,
그다음 세 번째로 작은 것 등..
예를 들어, 그림 1은 n=5 이고 2개의 컵은 쟁반 A에, B에는 아무것도 없고, C에는 3개가 있다.
처음 쟁반의 상태가 주어지면, 모든 컵들을 이동하여 쟁반 A나 C에 쌓을 수 있다.
컵을 이동할 때는 다음의 세 가지 규칙을 따른다.
규칙 1. 쟁반의 컵은 가장 위에 있는 컵만 다른 쟁반의 가장 위에 있는 컵 위에 쌓을 수 있다.
규칙 2. 큰 컵 위에 작은 컵은 쌓을 수 없다.
규칙 3. A에서 C, C에서 A로는 직접 이동할 수 없다.
따라서 직접 이동 가능한 것은 A에서 B, B에서 A, B에서 C, C에서 B 중 하나이다.
당신이 할 일은 N개의 컵과 정수 M이 주어질 때 쟁반 A에 M번 안에 모든 컵들을 쌓을 수 있는지를 결정하는 것이다.
가능하다면 최소 이동 횟수를 출력하고, 그렇지 않으면 -1을 출력한다.
입력형식
입력의 첫 번째 줄에는 컵의 개수 N(1≤N≤15)과, 이동가능횟수 M(1≤M≤15,000,000)이 공백으로 구분하여 입력된다.
그 다음 줄부터 4번째 줄까지 쟁반 A, B, C의 현재 상태가 들어오는데
각 줄의 첫 번째 값은 컵의 개수 k이고 두 번째부터 k개의 컵이 오름차순 정렬로 들어온다.
출력형식
출력은 한 줄로 이루어지는데 M번 안에 쟁반 A에 모든 컵을 쌓을 수 있다면 그 최소 횟수를 출력하고 불가능하면 -1을 출력한다.
입력 예복사하기 3 10 0 1 1 2 2 3 |
출력 예복사하기 9 |
입력 예복사하기 4 20 2 1 2 1 3 1 4 |
출력 예복사하기 3 |
입력 예복사하기 2 5 2 1 2 0 0 |
출력 예복사하기 0 |
입력 예복사하기 3 3 0 1 1 2 2 3 |
출력 예복사하기 -1 |