관리 메뉴
목록2025/09/02 (1)
개발자공부일기
2251번 - 물통(c++)
https://www.acmicpc.net/problem/2251 세 개의 물통 A, B, C가 있다. A, B, C 물통의 용량이 주어지고, 처음에는 C 물통에만 물이 가득 차 있다.이때 A 물통이 비어 있을 때, C 물통에 담겨 있을 수 있는 물의 양을 모두 구하는 문제다. 물이 다양하게 담겨있는 여러가지 경우의 수 를 따지는 BFS(너비 우선 탐색) 방법을 이용하는 문제다.핵심 아이디어상태 표현(A, B, C) 세 물통에 들어 있는 물의 양으로 상태를 표현한다.하지만 세 개 다 저장할 필요는 없다.왜냐하면 C = 전체 물의 양 - (A+B)로 항상 계산할 수 있기 때문이다.따라서 (A, B) 두 값만 저장하면 충분하다.상태 전이(물 붓기)물을 옮기는 경우의 수는 6가지다.A→B, A→C, B→A, ..
카테고리 없음
2025. 9. 2. 18:08