[오리지널] 어머니 의 우유 (상)

어머니 의 우유 (cow. cpp)
[제목 설명]
농민 존 은 세 개의 용량 이 각각 A, B, C 리터 의 통 이 고 A, B, C 는 각각 세 개의 1 에서 20 까지 의 정수 이다.
처음에는 A 와 B 통 이 비 었 고 C 통 은 우 유 를 가득 담 았 다.
때때로 존 은 우 유 를 한 통 에서 다른 통 으로 쏟 아서 통 이 가득 채 워 지 거나 원래 통 이 비 어 있 을 때 까지 부 었 다.절약 으로 우 유 를 잃 어 버 리 지 않 는 다.
존 이 A 통 이 비 었 을 때 C 통 에 남 은 우유 의 모든 가능성 을 찾아내 는 데 도움 을 주 는 프로그램 을 써 라.
【 입력 】
첫 번 째 줄: 세 개의 정수 A, B 와 C.
【 출력 】
첫 번 째 줄: A 통 이 비 었 을 때 C 통 의 우유 남 은 양의 모든 가능성 을 오름차 로 열거 합 니 다.
[샘플 입력]
2 5 10
[샘플 출력]
5 6 7 8 9 10
이 문 제 는 검색 으로 풀 수 있 습 니 다. 아래 에 제 가 제공 한 검색 코드 가 있 습 니 다.우 유 를 따 르 는 과정 을 함수 재 귀 로 모 의 하 는 것 이다.
폭력 적 인 검색 처럼 보인다.

#include
#include
#include
#include
#include
using namespace std;
const int maxn=21;
int sp,x,y,z;
bool ans[maxn];
bool t[maxn][maxn][maxn];
void fre()
{
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
}
void mov(int a,int b,int c)
{
	if(a==0 && c>=0) ans[c]=1;
	if(t[a][b][c]) return;
	t[a][b][c]=1;
	
	//c->a:mov(min(x,a+c),b,max(a+c-x,0));
	//mov(max(min(x,a+c)+b-y,0),min(y,b+min(x,a+c)),max(a+c-x,0));
	//mov(max(min(x,a+b),0),max(a+b-x,0),min(z,c+min(x,a+b)));
	mov(max(a+c-z,0),b,min(z,a+c));//a to c
	mov(min(x,a+c),b,max(a+c-x,0));//c to a
	mov(max(a+b-y,0),min(y,a+b),c);//a to b
	mov(min(x,a+b),max(a+b-x,0),c);// b to a
	mov(a,min(y,b+c),max(b+c-y,0));//b to c
	mov(a,max(b+c-z,0),min(z,b+c));// c to b
}
void out()
{
	for(int i=0;i<=maxn;i++)
	{
		if(ans[i]) 
		{
			if(sp) printf(" ");
			else sp++;
			printf("%d",i);
		}
	}
}
int main()
{  
	fre();
	scanf("%d %d %d",&x,&y,&z);
	mov(0,0,z);
	out();
	return 0;
}

검색 해 보 이 는 검색 (By xmy):

#include
bool vis[22][22][22],k[22];
int a[3];
void xmy(int x,int q,int y,int w,int z,int e)
{
	int b[3];
	b[q]=x,b[w]=y,b[e]=z;
	if(!b[0]) k[b[2]]=1;
	if(vis[b[0]][b[1]][b[2]]) return;
	vis[b[0]][b[1]][b[2]]=1;
	int f;
	for(int i=0;i<=2;i++)
		if(b[i])
			for(int j=0;j<=2;j++)
				if(i!=j)
				{
					for(f=0;f<3;f++) if(f!=i&&f!=j) break;
					if(b[i]>=a[j]-b[j]) xmy(b[i]-a[j]+b[j],i,a[j],j,b[f],f);
					else xmy(0,i,b[j]+b[i],j,b[f],f);
				}
}
int main()
{
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	scanf("%d%d%d",&a[0],&a[1],&a[2]);
	xmy(0,0,0,1,a[2],2);
	int i;
	for(i=0;i<=20;i++)
		if(k[i]) {printf("%d",i);break;}
	for(i++;i<=20;i++)
		if(k[i]) printf(" %d",i);
}