kthng

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으로 해결하는 방법도 가능하다.

boj 5623 : SUME https://www.acmicpc.net/problem/5623 단순한 수학문제인 것 같다.a0을 먼저 구하고 a1,a2...a(n-1)까지 구하면 됨. n = 2일 경우가 제일 문제인데, n = 2일 경우는 유일한 수열을 구할 수 없다.하지만20 22 0이 경우는 1 1로 유일하게 구할 수 있어서n = 2가 input으로 주어지면 1 1 을 출력해준다.(문제에서 유일한 경우만 주어지고, ai는 자연수라고 하였기 때문)