kthng

boj 2792 : LJUBOMORA https://www.acmicpc.net/problem/2792 DP로 풀릴 수 있는가 보느라 한참을 고민했다.하지만 의외로 간단하게 풀릴 수 있었음... [1 ~ 가장 많은 보석 수]에서 이분 탐색으로 찾는다.만약 보석을 적게 나눠준다면 모든 보석을 털 수 없다.보석을 모두 털 수 있는 최소 갯수가 정답. 예제의5 274 이 경우, 2개씩 나눠주면, 2 2 2 1 2 2로 6명이 있어야 하므로 모든 보석을 털 수 없다.3개씩 나눠주면 3 3 1 3 1로 5명에게 털 수 있다.따라서 5명에게 나눠주면 모든 보석을 털 수 있는 최소 보석수는 3개이다. 이 방법으로 해결하면 시간복잡도는 MlogM

boj 2981 : GRANICA https://www.acmicpc.net/problem/2981 고민을 좀 했던 문제이다. Aij를 ai와 aj(i != j)의 차이라고 할때모든 Aij의 공약수를 출력해주면 된다. 모든 Aij의 공약수는, a가 정렬되어있을 때, ai - a(i-1)의 공약수이다.( gcd(a,b) = gcd(a + b, b) ) 답은 공약수들을 정렬하여 출력하면 된다.(영문은 any order라고 되어있는데 ㅜㅜㅜ...)

boj 4198 : Trainsorting https://www.acmicpc.net/problem/4198 증가 부분수열, 감소 부분수열 을 이용하여 해결한다.(n번째부터 시작하는 증가부분수열의 갯수) + (n번째부터 시작하는 감소부분수열의 갯수) - 1 의 최대값이 정렬된 train car의 최대 갯수.시간복잡도는 n^2으로 하여 간단하게 풀었지만 nlogn으로 해결하는 방법도 가능하다.