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는 자연수라고 하였기 때문)

boj 5624 : DOBRI https://www.acmicpc.net/problem/5624 삼성 코드그라운드의 좋은수 라는 문제와 유사하다.N의 범위가 [-100000,100000]이라는 데서 힌트를 얻을 수 있다.i번째 숫자가 세 수의 합으로 이루어져있는지 확인하기 위해서 일반적으로 코딩을 한다면 N^3으로 가뿐하게 시간초과가 나지만,(i번째 숫자) - (i보다 먼저 오는 숫자)가 두 수의 합으로 이루어져있는지 확인하는 방법으로 코딩을하면 N^2만에 해결할 수 있다.이 방법으로 해주기 위해 두 수의 합으로 이루어져있는지 확인하는 -100000~100000범위의 bool 배열을 이용한다.