눈금이 없는 물통 두 개가 있다. A 통에는 A리터, B 통에는 B리터까지 담긴다.
처음에는 두 통이 모두 비어 있고, 한 번에 다음 여섯 동작 가운데 하나를 할 수 있다. 동작마다 번호가 있다.
- 1: A 통을 수도에서 가득 채운다. 2: B 통을 가득 채운다.
- 3: A 통을 모두 쏟아 버린다. 4: B 통을 모두 쏟아 버린다.
- 5: A 통의 물을 B 통에 붓는다. A 통이 비거나 B 통이 가득 찰 때까지 붓고, 물은 넘치지도 사라지지도 않는다.
- 6: B 통의 물을 A 통에 같은 방법으로 붓는다.
두 통 가운데 어느 한쪽에 딱 t리터가 담기게 하는 가장 짧은 동작 순서를 구하라.
가장 짧은 순서가 여럿이면, 동작 번호를 앞에서부터 견주어 처음으로 다른 자리에서 번호가 작은 순서를 고른다.
답은 동작 수 k를 먼저 쓰고, 이어서 동작 번호 k개를 차례대로 쓴다.
처음부터 한쪽에 t리터가 있으면(t = 0) 0만 출력한다. 어떻게 해도 안 되면 -1을 출력한다.
입력
첫 줄에 물음의 수 q(1 ≤ q ≤ 20). 다음 q줄에 A, B, t(1 ≤ A, B ≤ 90, 0 ≤ t ≤ 90)
출력
물음마다 한 줄에 "k 동작1 … 동작k"(빈칸 하나로 띄움), 또는 -1
예시 1 · stdin
4
3 5 4
2 4 3
7 7 0
1 4 2
stdout
6 2 6 3 6 2 6
-1
0
4 1 5 1 5
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
두 통에 든 양 (a, b)를 칸 하나로 보면, 동작 한 번이 칸에서 칸으로 가는 한 걸음이에요. 가장 짧은 순서는 너비 우선 탐색(BFS)으로 찾아요. 큐에서 앞의 것을 꺼내고 새 칸을 뒤에 넣으면 0걸음 칸, 1걸음 칸, 2걸음 칸 차례로 나오므로 목표 칸을 처음 꺼낼 때가 가장 짧아요. 칸마다 '처음 들어온 앞 칸'과 '그때 한 동작'을 적어 두었다가, 목표 칸에서 앞 칸을 따라 (0, 0)까지 거슬러 가면 순서가 나와요. 동작을 1번부터 차례로 해 보고 처음 닿을 때만 적으면, 같은 걸음 수의 칸들이 번호가 앞선 순서대로 큐에 들어가서 저절로 번호가 앞선 순서가 골라져요. 칸은 많아야 91 × 91개라, (a, b)를 수 하나 a * (B + 1) + b로 바꿔 목록 하나에 적으면 돼요. 큐는 언어마다 달라요. Python collections.deque의 popleft(), Java ArrayDeque의 add·poll, C# Queue<T>의 Enqueue·Dequeue, C++ std::queue의 push·front·pop이에요. C에는 큐가 없어서 배열과 머리·꼬리 번호로 만들고, JS·TS는 shift()가 앞을 빼느라 느릴 수 있어서 배열에 머리 번호를 두고 옮겨요. 크레이콘도 목록에 넣기로 넣고 머리 번호를 옮기며, 새목록에 앞 칸과 동작을 적어요. '못 찾음'은 Python None, JS·TS·Java·C# null, C++ std::optional, 크레이콘 빈값으로 돌려줘요. 함정 여섯: ① 뒤에서 꺼내면(Python pop()) 스택이 되어 깊이 우선 탐색이 되고, 처음 찾은 길이 가장 짧은 길이 아니에요. Java ArrayDeque의 push·pop은 둘 다 앞쪽을 써서 똑같이 스택이 돼요. ② 부을 양은 min(a, B − b)예요. 받는 통이 넘칠 때 남은 물을 버리면(붓는 통을 0으로) 만들 수 있는 양이 달라져요. ③ 목표를 새로 넣는 칸에서만 확인하면 시작 칸 (0, 0)을 놓쳐서 t = 0에 0이 아니라 동작 하나를 답해요. ④ 목표는 '어느 한쪽'이라 B 통만 t인 경우도 답이에요. ⑤ 앞 칸을 따라 모은 동작은 끝에서 처음 쪽으로 거꾸로 나와요. 뒤집어서 출력해요(Python [::-1], JS·TS reverse(), Java Collections.reverse, C# List.Reverse(), C++ std::reverse, 크레이콘 뒤집기()). ⑥ 동작을 번호 차례로 해 보지 않으면(예를 들어 B 쪽을 먼저), A 쪽과 B 쪽에 같은 길이의 길이 있을 때(1 4 2처럼) 다른 순서를 내요.
Pythonmain.py · 36 줄
from collections import dequedef shortest_plan(A, B, t): """빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 None.""" w = B + 1 # 상태 (a, b)를 수 하나 a * w + b로 적는다 prev = [-1] * ((A + 1) * w) # 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) move = [0] * ((A + 1) * w) # 그때 한 동작 번호 prev[0] = 0 queue = deque([0]) while queue: s = queue.popleft() a, b = divmod(s, w) if a == t or b == t: # 꺼낸 차례가 곧 가깝고 앞선 차례다 plan = [] while s != 0: # 앞 상태를 따라가면 끝에서 처음 쪽으로 거꾸로 나온다 plan.append(move[s]) s = prev[s] return plan[::-1] ab = min(a, B - b) # A에서 B로 부을 수 있는 양 ba = min(b, A - a) # B에서 A로 부을 수 있는 양 nexts = [(A, b), (a, B), (0, b), (a, 0), (a - ab, b + ab), (a + ba, b - ba)] for k, (na, nb) in enumerate(nexts, start=1): # 동작 번호가 작은 것부터 n = na * w + nb if prev[n] < 0: # 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s move[n] = k queue.append(n) return Noneq = int(input())for _ in range(q): A, B, t = map(int, input().split()) plan = shortest_plan(A, B, t) print(-1 if plan is None else " ".join(map(str, [len(plan)] + plan)))
JavaScriptmain.js · 41 줄
const lines = require("fs").readFileSync(0, "utf8").trim().split("\n");// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 nullfunction shortestPlan(A, B, t) { const w = B + 1; // 상태 (a, b)를 수 하나 a * w + b로 적는다 const prev = new Array((A + 1) * w).fill(-1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) const move = new Array((A + 1) * w).fill(0); // 그때 한 동작 번호 prev[0] = 0; const queue = [0]; for (let head = 0; head < queue.length; head++) { // shift() 대신 머리 번호를 옮긴다 let s = queue[head]; const a = Math.floor(s / w); const b = s % w; if (a === t || b === t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 const plan = []; for (; s !== 0; s = prev[s]) plan.push(move[s]); // 끝에서 처음 쪽으로 거꾸로 나온다 return plan.reverse(); } const ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 const ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 const nexts = [[A, b], [a, B], [0, b], [a, 0], [a - ab, b + ab], [a + ba, b - ba]]; nexts.forEach(([na, nb], k) => { // 동작 번호(k + 1)가 작은 것부터 const n = na * w + nb; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } }); } return null;}const q = Number(lines[0]);const out = [];for (let i = 1; i <= q; i++) { const [A, B, t] = lines[i].trim().split(" ").map(Number); const plan = shortestPlan(A, B, t); out.push(plan === null ? "-1" : [plan.length, ...plan].join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 42 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split("\n");// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 nullfunction shortestPlan(A: number, B: number, t: number): number[] | null { const w = B + 1; // 상태 (a, b)를 수 하나 a * w + b로 적는다 const prev: number[] = new Array((A + 1) * w).fill(-1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) const move: number[] = new Array((A + 1) * w).fill(0); // 그때 한 동작 번호 prev[0] = 0; const queue: number[] = [0]; for (let head = 0; head < queue.length; head++) { // shift() 대신 머리 번호를 옮긴다 let s = queue[head]; const a = Math.floor(s / w); const b = s % w; if (a === t || b === t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 const plan: number[] = []; for (; s !== 0; s = prev[s]) plan.push(move[s]); // 끝에서 처음 쪽으로 거꾸로 나온다 return plan.reverse(); } const ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 const ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 const nexts: [number, number][] = [[A, b], [a, B], [0, b], [a, 0], [a - ab, b + ab], [a + ba, b - ba]]; nexts.forEach(([na, nb], k) => { // 동작 번호(k + 1)가 작은 것부터 const n = na * w + nb; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } }); } return null;}const q = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= q; i++) { const [A, B, t] = lines[i].trim().split(" ").map(Number); const plan = shortestPlan(A, B, t); out.push(plan === null ? "-1" : [plan.length, ...plan].join(" "));}console.log(out.join("\n"));
JavaMain.java · 66 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.StringTokenizer;public class Main { // 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 null // 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 static List<Integer> shortestPlan(int A, int B, int t) { int w = B + 1; int[] prev = new int[(A + 1) * w]; // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) int[] move = new int[(A + 1) * w]; // 그때 한 동작 번호 Arrays.fill(prev, -1); prev[0] = 0; ArrayDeque<Integer> queue = new ArrayDeque<>(); queue.add(0); while (!queue.isEmpty()) { int s = queue.poll(); // 앞에서 꺼낸다(add는 뒤에 넣는다) int a = s / w, b = s % w; if (a == t || b == t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 List<Integer> plan = new ArrayList<>(); for (; s != 0; s = prev[s]) plan.add(move[s]); // 끝에서 처음 쪽으로 거꾸로 Collections.reverse(plan); return plan; } int ab = Math.min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = Math.min(b, A - a); // B에서 A로 부을 수 있는 양 int[][] nexts = {{A, b}, {a, B}, {0, b}, {a, 0}, {a - ab, b + ab}, {a + ba, b - ba}}; for (int k = 0; k < 6; k++) { // 동작 번호(k + 1)가 작은 것부터 int n = nexts[k][0] * w + nexts[k][1]; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.add(n); } } } return null; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); int A = Integer.parseInt(st.nextToken()); int B = Integer.parseInt(st.nextToken()); int t = Integer.parseInt(st.nextToken()); List<Integer> plan = shortestPlan(A, B, t); if (plan == null) { out.append(-1).append('\n'); continue; } out.append(plan.size()); for (int k : plan) out.append(' ').append(k); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 58 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ // 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 null // 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 static List<int>? ShortestPlan(int A, int B, int t) { int w = B + 1; var prev = Enumerable.Repeat(-1, (A + 1) * w).ToArray(); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) var move = new int[(A + 1) * w]; // 그때 한 동작 번호 prev[0] = 0; var queue = new Queue<int>(); queue.Enqueue(0); while (queue.Count > 0) { int s = queue.Dequeue(); int a = s / w, b = s % w; if (a == t || b == t) // 꺼낸 차례가 곧 가깝고 앞선 차례다 { var plan = new List<int>(); for (; s != 0; s = prev[s]) plan.Add(move[s]); // 끝에서 처음 쪽으로 거꾸로 plan.Reverse(); return plan; } int ab = Math.Min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = Math.Min(b, A - a); // B에서 A로 부을 수 있는 양 var nexts = new[] { (A, b), (a, B), (0, b), (a, 0), (a - ab, b + ab), (a + ba, b - ba) }; for (int k = 0; k < 6; k++) // 동작 번호(k + 1)가 작은 것부터 { int n = nexts[k].Item1 * w + nexts[k].Item2; if (prev[n] < 0) // 처음 닿을 때만 적는다(넣을 때 표시) { prev[n] = s; move[n] = k + 1; queue.Enqueue(n); } } } return null; } static void Main() { int q = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int i = 0; i < q; i++) { int[] p = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); var plan = ShortestPlan(p[0], p[1], p[2]); output.Append(plan == null ? "-1" : string.Join(" ", plan.Prepend(plan.Count))).Append('\n'); } Console.Write(output); }}
C++main.cpp · 56 줄
#include <algorithm>#include <iostream>#include <optional>#include <queue>#include <vector>// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 빈 optional// 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다std::optional<std::vector<int>> shortestPlan(int A, int B, int t) { int w = B + 1; std::vector<int> prev((A + 1) * w, -1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) std::vector<int> move((A + 1) * w, 0); // 그때 한 동작 번호 std::queue<int> queue; prev[0] = 0; queue.push(0); while (!queue.empty()) { int s = queue.front(); // front()로 읽고 pop()으로 뺀다 queue.pop(); int a = s / w, b = s % w; if (a == t || b == t) { // 꺼낸 차례가 곧 가깝고 앞선 차례다 std::vector<int> plan; for (; s != 0; s = prev[s]) plan.push_back(move[s]); // 끝에서 처음 쪽으로 거꾸로 std::reverse(plan.begin(), plan.end()); return plan; } int ab = std::min(a, B - b); // A에서 B로 부을 수 있는 양 int ba = std::min(b, A - a); // B에서 A로 부을 수 있는 양 int nexts[6][2] = {{A, b}, {a, B}, {0, b}, {a, 0}, {a - ab, b + ab}, {a + ba, b - ba}}; for (int k = 0; k < 6; k++) { // 동작 번호(k + 1)가 작은 것부터 int n = nexts[k][0] * w + nexts[k][1]; if (prev[n] < 0) { // 처음 닿을 때만 적는다(넣을 때 표시) prev[n] = s; move[n] = k + 1; queue.push(n); } } } return std::nullopt;}int main() { int q; std::cin >> q; while (q--) { int A, B, t; std::cin >> A >> B >> t; auto plan = shortestPlan(A, B, t); if (!plan) { std::cout << -1 << '\n'; continue; } std::cout << plan->size(); for (int k : *plan) std::cout << ' ' << k; std::cout << '\n'; }}
Cmain.c · 61 줄
#include <stdio.h>#define MAXS (91 * 91)static int prev[MAXS]; /* 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) */static int move[MAXS]; /* 그때 한 동작 번호 */static int queue[MAXS]; /* 상태마다 한 번만 들어가니 이 크기면 된다 */static int plan[MAXS];static int min(int x, int y) { return x < y ? x : y; }/* 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호(가장 앞선 것)를 plan에 채우고 개수를 돌려준다. 안 되면 -1 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다 */static int shortest_plan(int A, int B, int t) { int w = B + 1; for (int s = 0; s < (A + 1) * w; s++) prev[s] = -1; int head = 0, tail = 0; prev[0] = 0; queue[tail++] = 0; while (head < tail) { int s = queue[head++]; int a = s / w, b = s % w; if (a == t || b == t) { /* 꺼낸 차례가 곧 가깝고 앞선 차례다 */ int len = 0; for (; s != 0; s = prev[s]) plan[len++] = move[s]; /* 끝에서 처음 쪽으로 거꾸로 */ for (int i = 0, j = len - 1; i < j; i++, j--) { int tmp = plan[i]; plan[i] = plan[j]; plan[j] = tmp; } return len; } int ab = min(a, B - b); /* A에서 B로 부을 수 있는 양 */ int ba = min(b, A - a); /* B에서 A로 부을 수 있는 양 */ int na[6] = {A, a, 0, a, a - ab, a + ba}; int nb[6] = {b, B, b, 0, b + ab, b - ba}; for (int k = 0; k < 6; k++) { /* 동작 번호(k + 1)가 작은 것부터 */ int n = na[k] * w + nb[k]; if (prev[n] < 0) { /* 처음 닿을 때만 적는다(넣을 때 표시) */ prev[n] = s; move[n] = k + 1; queue[tail++] = n; } } } return -1;}int main(void) { int q; scanf("%d", &q); while (q--) { int A, B, t; scanf("%d %d %d", &A, &B, &t); int len = shortest_plan(A, B, t); printf("%d", len); for (int i = 0; i < len; i++) printf(" %d", plan[i]); printf("\n"); } return 0;}
Craykonmain.cray · 59 줄
// 빈 두 물통에서 한쪽에 딱 t리터를 담는 가장 짧은 동작 번호 목록(가장 앞선 것). 안 되면 빈값// 상태 (a, b)는 수 하나 a * (B + 1) + b로 적는다가장짧은계획(A, B, t){ w = B + 1; prev = 새목록((A + 1) * w, -1); // 그 상태로 처음 들어온 앞 상태(-1이면 아직 못 가 봄) move = 새목록((A + 1) * w, 0); // 그때 한 동작 번호 prev[0] = 0; queue = [0]; head = 0; // 목록 앞에서 빼지 않고 머리 번호를 옮긴다 동안 (head < queue.개수) { s = queue[head]; head += 1; a = 수학.몫(s, w); b = s % w; 만약 (a == t || b == t) { plan = []; 동안 (s != 0) { plan.넣기(move[s]); s = prev[s]; } plan.뒤집기(); 돌려주기 plan; } ab = 수학.작은수(a, B - b); // A에서 B로 부을 수 있는 양 ba = 수학.작은수(b, A - a); // B에서 A로 부을 수 있는 양 nexts = [A * w + b, a * w + B, b, a * w, (a - ab) * w + b + ab, (a + ba) * w + b - ba]; 반복 (k = 0; k < 6; k++) { n = nexts[k]; 만약 (prev[n] < 0) { prev[n] = s; move[n] = k + 1; queue.넣기(n); } } } 돌려주기 빈값;}q = 콘솔.줄읽기().공백제거().수로변환();반복 (i = 0; i < q; i++){ p = 콘솔.수들읽기(); plan = 가장짧은계획(p[0], p[1], p[2]); 만약 (plan == 빈값) { 콘솔.쓰기(-1); } 아니면 { plan.끼우기(0, plan.개수); 콘솔.쓰기(plan.잇기(" ")); }}