graph 2

BOJ 14867 물통

https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 간단한 bfs로 풀 수 있는 문제입니다. state의 범위가 크기 때문에 배열이 아닌 set으로 메모이제이션을 해주면 됩니다. 상태가 그렇게 많지 않을 거라는 믿음을 가지고 짜서 맞았는데, 왜 되는지는 잘 모르겠습니다. 믿음을 가지는 게 생각보다 어려운 거 같습니다. +) cologne 님이 알려주셨습니다. 액션을 한 번 하면 둘 중에 한 물통은 비어..

BOJ 8872 빌라봉

https://www.acmicpc.net/problem/8872 8872번: 빌라봉 첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. N: 빌라봉의 개수 M: 이미 존재하는 길들의 개수 L: 뱀이 새로 지어진 길을 통행하는데 걸리는 시간 (일 단위). A, B, www.acmicpc.net 설명이 조금 길지만 정리해보면 포레스트가 주어질 때, 정점들을 잘 이어 트리로 만들면서 트리의 지름이 가장 작게 하면 됩니다. 트리의 지름을 사용하는 문제를 오랜만에 봐서 새로웠습니다. 이 문제를 풀기 위해서는 그리디한 방법을 사용할 수 있습니다. 임의의 트리 두 개를 이을 때, 각 트리의 지름에 중간에 있는 중점끼리 이어주는 것이 새로 만들어지는 트리의 지름을 ..