문제

풀이 과정

완전 탐색 문제.
뭔가 순열을 활용한 문제라고 생각했으나, 갑자기 "어 이거! 뭔가 하노이의 탑 이다" 라는 생각이 들어 도전했다가 시간만 엄청 낭비한 문제. 결과적으로 미리 말하자면 하노이의 탑이랑 비슷한 부분은 있지만 하노이의 탑은 아니다. 하노이의 탑은 원판의 갯수에 따라 값이 달라지기 때문.

알고리즘 문제는 내가 생각한 식 가운데 가장 정답을 구하기 쉬운거로 가자. 최적화된 알고리즘 같은 거 아직 쓸 줄 모른다. 어떤 식을 쓰든 간에 문제를 해결한다에 집중하자.

문제 풀이는 다음과 같다.

1. 세가지에서 두 항목을 정해 만들 수 있는 모든 경우의 수는 6개이다.
2. 6개의 경우의 수에서, A==0 일때 C가 채워져 있는 경우를 찾는다.
3. 단, 두가지의 경우가 존재한다. 옮기는 물의 양이 옮겨지는 컵의 양보다 커서 옮기는 물이 남는 경우와, 이와 반대로 옮기는 물의 양이 남지 않고 모두 옮겨지는 물의 양에 넣어지는 경우를 따로 탐색해봐야한다.

정답

import java.util.Scanner;

public class Main {
    static boolean[][] visited = new boolean[201][201];
    static boolean[] ans = new boolean[201];
    static int A, B, C;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        A = sc.nextInt();
        B = sc.nextInt();
        C = sc.nextInt();
        
        DFS(0, 0, C);
        for(int i = 0; i<201; i++) if(ans[i]) System.out.print(i + " ");
    }

    public static void DFS(int a, int b, int c) {
        if (visited[a][b]) return;
        visited[a][b] = true;

        if (a == 0) ans[c] = true;
        int sum = a + b;
        if (sum > B) DFS(sum - B, B, c);
        else DFS(0, sum, c);

        sum = b + a;
        if (sum > A) DFS(A, sum - A, c);
        else DFS(sum, 0, c);
        
        sum = a + c;
        if (sum > C) DFS(sum - C, b, C);
        else DFS(0, b, sum);
        
        sum = c + a;
        if (sum > A) DFS(A, b, sum - A);
        else DFS(sum, b, 0);
        
        sum = b + c;
        if (sum > C) DFS(a, sum - C, C);
        else DFS(a, 0, sum);

        sum = c + b;
        if (sum > B) DFS(a, B, sum-B);
        else DFS(a, sum,0);
    }
}