BOJ(물통)(2251)

작성일 | In

물통 2251

  • 세 물통 A,B,C가 있을 때,
  • C만 가득 차있다.
  • 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 앞의 물통이 빌 때까지 붓거나, 뒤의 물통이 가득 찰 때까지 붓게 된다
  • 이 과정에서 손실되는 물이 없다

  • 이 때 A가 비어있을 때, C에 들어있을 수 있는 양을 모두 구하는 문제

  • 3차원 배열을 만들 필요는 없다.

  • 중간에 물이 손실되지 않기 때문에,C에 들어있는 양을 N이라고 하면 N-A-B로 풀 수 있다.

  • 방법은 여러가지가 있다.
  • 아래는 일반화된 방법
  • 물통을 0,1,2로 한다음에 6가지 밖에 없기 때문에
  • 그 경우를 전부 일반화 해서 구현할 수 있다.
from collections import deque
moves = list(zip([0,0,1,1,2,2], [1,2,0,2,0,1]))
ans = [False]*201
check = [[False]*201 for _ in range(201)]
cap = list(map(int,input().split()))
sum = cap[2]
q = deque()
q.append((0,0))
check[0][0] = True
ans[cap[2]] = True
while q:
    now = q.popleft()
    cur = [now[0], now[1], sum-now[0]-now[1]]
    for f, t in moves:
        next = cur[:]
        next[t] += next[f]
        next[f] = 0
        if next[t] >= cap[t]:
            next[f] = next[t] - cap[t]
            next[t] = cap[t]
        if not check[next[0]][next[1]]:
            check[next[0]][next[1]] = True
            q.append((next[0],next[1]))
            if next[0] == 0:
                ans[next[2]] = True
for i in range(0, cap[2]+1):
    if ans[i]:
        print(i, end=' ')
print()
  • A가 비어있을 때마 C에 들어있을 수 있는 양을 모두 구하는 문제

참고자료 codeplus

0%