문제:
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력:
첫째 줄에 세 정수 A, B, C가 주어진다.
출력:
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
풀이방법:
A, B를 담을 수 있는 물통들을 기준으로 하여 visited 배열을 만들고, BFS를 수행하도록 한다. visited의 가능한 갯수는 A와 B에 담을 수 있는 경우의 수와 같다. 처음은 비어있기 때문에, (0,0)으로부터 시작하도록 한다. 매 C는 가지고 있는 A, B 물의 양을 통해 구하도록 한다. 가지고 있는 A, B, C 물의 양을 통해 이동할 수 있는 모든 경우에 대해 조사하도록 한다. (A-> B, A-> C, B->C, B-> A, C-> A, C-> B)와 같은 총 6가지 case가 존재한다. 가능한 모든 경우에 대해 BFS를 수행하며 A의 물의 양이 0인 경우에 C의 값을 저장하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
from collections import deque
A, B, C = map(int,input().split())
queue = deque()
queue.append((0,0))
visited = [[0 for _ in range(B+1)] for _ in range(A+1)]
visited[0][0] = 1
answer = []
while queue:
x,y = queue.popleft()
z = C-x-y
if x==0:
answer.append(z)
#A->B
water = min(x,B-y)
if not visited[x-water][y+water]:
visited[x-water][y+water] = 1
queue.append((x-water,y+water))
#A->C
water = min(x,C-z)
if not visited[x-water][y]:
visited[x-water][y] = 1
queue.append((x-water,y))
#B->C
water = min(y,C-z)
if not visited[x][y-water]:
visited[x][y-water] = 1
queue.append((x,y-water))
#B->A
water = min(y,A-x)
if not visited[x+water][y-water]:
visited[x+water][y-water] = 1
queue.append((x+water,y-water))
#C->A
water = min(z,A-x)
if not visited[x+water][y]:
visited[x+water][y] = 1
queue.append((x+water,y))
#C->B
water = min(z,B-y)
if not visited[x][y+water]:
visited[x][y+water] = 1
queue.append((x,y+water))
print(*sorted(answer))
|
cs |
문제링크:
https://www.acmicpc.net/problem/2251
2251번: 물통
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]11058. 크리보드 (0) | 2021.11.01 |
|---|---|
| [BOJ]14391. 종이 조각 (0) | 2021.10.29 |
| [BOJ] 15988. 1, 2, 3 더하기 (0) | 2021.10.25 |
| [BOJ] 13023. ABCDE (0) | 2021.10.22 |
| [BOJ]1339. 단어 수학 (0) | 2021.10.21 |