블로그 이사 중입니다 >> gumgood.github.io

https://www.acmicpc.net/category/detail/1935 A. BOJ 16282 Black Chain 첫 번째 접근법은 'n개의 고리가 연결된 체인에서 m개의 고리를 풀 때 1g부터 ng까지 모든 무게를 생성할 수 있는지' 여부를 판단하는 함수 f를 만들어 풀어야 할 고리의 최소값을 binary search로 찾는 것이었습니다. f를 만들어낸 방법은 다음과 같습니다. m개의 고리를 풀면 1g 고리가 m개가 생성되므로 일단 이것만으로 1g부터 mg까지 모두 생성이 가능합니다. 남은 (n-m)g의 체인은 m+1개 이하의 체인들로 나눌 수 있습니다. 여기서 나눈 체인들은 앞에서 푼 고리 사이에 들어간다고 생각하시면 됩니다. 1g ~ mg의 무게를 만들 수 있을 때, (m+1)g의 체인이..