kth990303의 코딩 블로그

스터디그룹에서 연습 C번으로 진행된 문제. 어떻게 보면 되게 쉽지만, 어떻게 보면 마냥 쉽지만은 않은 문제. 문제는 아래와 같다. 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 의식의 흐름 및 해설 물통 물 양이 각각 C, D가 되기 위한 최소 횟수를 구하는 문제. 이런 유형은 보통 BFS로 접근하는데, 문제는 N이 최대 10만이라 이차원배열로 방문체크를 하면 무조건 시간초과 혹은 메모리초과가 난..

그룹원 한분께서 요청해주신 문제를 해결하면서 degree sequence 라는 개념을 알게 됐다. Warming Up 요청해주셨던 문제는 아래와 같다. 한 번 풀어보도록 하자. (degree sequence 개념을 몰라도 해결이 가능하다.) https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net 불만을 최소화하기 위해서는 최소한의 다리로 건물을 연결해야 하며, 따라서 mst를 금방 떠올릴 수 있다. 그러나, 단순 mst 문제는 아니고, 차수에 따라 답이 달..