190116 BOJ (2251) 물통

2019-01-16

2251. 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10
풀이 과정
  • 출처를 참고해서 풀었음
  • 모든 경우를 탐색해야 함
  • 물통이 비워질때까지 붓거나/ 다른 물통이 가득 찰 때 까지만 물을 부을 수 있음을 생각해야 함
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

    public static void main(String args[]) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
            String[] tmp=br.readLine().split(" ");
            A=Integer.parseInt(tmp[0]);
            B=Integer.parseInt(tmp[1]);
            C=Integer.parseInt(tmp[2]);
            dfs(0,0,C);

            for(int i=0;i<201;i++){
                if(ans[i])
                    sb.append(i+" ");
            }
            System.out.print(sb);
    }
    public static void dfs(int a,int b,int c){
        if(visited[a][b]) return;

        if(a==0)
            ans[c]=true;
        visited[a][b]=true;

        // a -> b
        if(a+b>B){
            dfs(a+b-B,B,c);
        }else{
            dfs(0,a+b,c);
        }

        // b -> a
        if(a+b>A){
            dfs(A,a+b-A,c);
        }else{
            dfs(a+b,0,c);
        }

        // c -> a
        if(a+c>A){
            dfs(A,b,a+c-A);
        }else{
            dfs(a+c,b,0);
        }

        // c -> b
        if(b+c>B){
            dfs(a,B,b+c-B);
        } else{
            dfs(a,b+c,0);
        }

        dfs(a,0,b+c);
        dfs(0,b,a+c);

    }
}