물통 > 문제은행

본문 바로가기


문제은행

3078 : 물통

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



용량이 다른 두 개의 빈 물통 A, B가 있다. 이 물통들에 물을 채우고 비우는 일을 반복하여 두 물통을 원하는 상태 (목표하는 양의 물을 담은 상태)가 되도록 만들고자 한다. 물통 이외에는 물의 양을 정확히 잴 수 있는 방법이 없으며, 가능한 작업은 다음과 같은 세 종류가 전부이다.

 

[F(x): Fill x]: 물통 x에 물을 가득 채 운다. (물을 채우기 전에 물통 x가 비어 있는지 여부는 관계없음. 다른 물통은 그대로 둠)

 

[E(x): Empty x]: 물통 x의 물을 모두 버린다. (다른 물통은 그대로 둠)

 

[M(x,y): Move water from x to y)]: 물통 x의 물을 물통 y에 붓는다. 이때 만약 물통 x에 남아 있는 물의 양이 물 통 y에 남아 있는 빈 공간보다 적거나 같다면 물통 x의 물을 물통 y에 모두 붓는다. 만약 물통 x에 남아 있는 물의 양이 물통 y에 남아 있는 빈 공간보다 많다면 부을 수 있는 만큼 최대로 부어 물통 y를 꽉 채우고 나머지는 물통 x에 남긴다.

 

예를 들어, 물통 A와 B의 용량이 각각 2리터와 5리터라고 하자. 두 물통 모두 빈 상태에서 시작하여 최종적으로 물통 A에는 2리터, 물통 B에는 4리터 물을 남기길 원할 경우, 다음과 같은 순서로 작업을 수행하면 총 8회의 작업으로 원하는 상태에 도달할 수 있다.

 

(0,0)→[F(B)]→(0,5)→[M(B,A)]→(2,3)→[E(A)]→(0,3)→[M(B,A)]→(2,1)→[E(A)]→(0,1)→[M(B,A)]→(1,0)→[F(B)]→(1,5) →[M(B,A)]→(2,4)

 

하지만, 작업 순서를 아래와 같이 한다면 필요한 작업 총 수가 5회가 된다.

 

(0,0)→[F(A)]→(2,0)→[M(A,B)]→(0,2)→ [F(A)]→(2,2)→[M(A,B)]→(0,4)→[F(A)]→(2,4)

 

두 물통의 용량과 원하는 최종 상태를 입력으로 받은 후, 두 물통이 비어 있는 상태에서 시작하여 최종 상태에 도달하기 위한 최소 작업 수를 구하는 프로그램을 작성하시오.
 


표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최종 상태에서 물통 B에 남겨야 하는 물의 용량을 나타내는 정수 d(0 ≤ d ≤ b)가 공백으로 분리되어 한 줄에 주어진다.


목표 상태에 도달하는 최소 작업 수를 나타내는 정수를 표준 출력으로 출력한다. 만약 목표 상태 에 도달하는 방법이 없다면 –1을 출력한다.

부분문제의 제약 조건 
● 부분문제 1: 전체 점수 100점 중 9점에 해당하며 A 물통의 용량은 1리터이다. 
● 부분문제 2: 전체 점수 100점 중 14점에 해당하며 B 물통의 용량은 A 물통의 용량의 배수이다. 
● 부분문제 3: 전체 점수 100점 중 34점에 해당하며 a,b의 범위를 1 ≤ a, b ≤ 1,000 으로 제한한다.
● 부분문제 4: 전체 점수 100점 중 43점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
3 7 3 2
[Copy]
9


[Copy]
2 5 0 1
[Copy]
5


[Copy]
3 5 2 4
[Copy]
-1




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.